c-gcd

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

Bob is interested in GCDs (Greatest Common Divisors). Formally, for some positive integers (a1,...,ak)(a_1,...,a_k)(a1​,...,ak​), we denote gcd⁡(a1,...,ak)gcd (a_1,...,a_k)gcd(a1​,...,ak​) as the greatest positive integer ddd, such that d∣aid|a_id∣ai​ for each 1≤i≤k1leq ileq k1≤i≤k.

Bob has chosen an interval [l,r][l,r][l,r]. He is going to choose kkk distinct integers from the interval and compute their GCD. There are many integers that can be the final answer, and Bob is curious in the number of such integers. Please write a program to tell him the answer.

The first and only line of input consists of three integers l,r,k(1≤l≤r≤1012,2≤k≤r−l+1)l, r, k(1leq lleq rleq 10^{12},2leq kleq r-l+1)l,r,k(1≤l≤r≤1012,2≤k≤r−l+1).

Print a single integer, indicating your answer.

示例1

复制5 9 2

5 9 2

复制3

3

思路：想找出来l-r这个区间内，挑k个数求gcd有几种不同的结果，我们可以换一种思路，找在l-r这个区间内能找到至少k个数的最大因数。比如l=5，r=9，我们找这个区间内能找到至少k=2个数的最大因数是3（当是3的时候找到6和9），因为小于这个数的所有数也满足在l-r这个区间内能找到至少k个数是他的倍数，所以1.2也满足。当我们找4的时候，只能找到8一个数是4的倍数，那么4就不满足在区间l-r里能找到至少两个数是他的倍数，那么就不满足题意，最后是1.2.3三种公约数。

当我们找的时候，注意把区间分成1~l-1和l~r两个区间找满足至少k个数的最大因数，然后分别减去左边界再相加就是我们求的不同gcd的个数。

#include
#include
#include

using namespace std;
typedef long long ll;
ll o,p,k;
bool cheek(ll x){
	return p/x-(o-1)/x>=k;
}
ll sove(ll x,ll y){
	ll l=x;
	ll r=y;
	ll ans=x-1;
	while(l<=r){
		ll mid=(l+r)/2;
		if(cheek(mid)){
			l=mid+1;
			ans=mid;
		}else{
			r=mid-1;
		}
	}
	return ans-x+1;
}
int main(){
	cin>>o>>p>>k;
	printf("%lld",sove(1,o-1)+sove(o,p));
	return 0;
}