2021年ICPC国际大学生程序设计竞赛暨陕西省第九届大学生程序设计竞赛 C-GCD(二分)

 题目大意：

输入三个整数l,r,k表示在区间[l,r]内找出有多少种k个数的最大公约数都是同一个数的集合 ，每种集合的最大公约数是不一样的。

思路：

要求多少种这样的集合就是求有多少个这样的最大公约数，如l,r,k分别为5 10 2，那么在[1,4]中有这样的最大公约数1,2,3;在[5,10]中有这样的最大公约数5；最后输出4。而这两个区间中的这样的最大公约数都是从小到大连续的，鉴于本题的数据量可以用二分分别在这两个区间中找出分别最大的这样的最大公约数是多少。

AC代码：

#includeusing namespace std;#define int long longint a,b,k,ans;bool check(int gcd){//如果区间[a,b]内存在是gcd的倍数的数大于或等于k个则返回true return (b/gcd-(a-1)/gcd)>=k;}int halfMaxNum(int l,int r)//用二分找出这样的最大公约数的数量 {int tl=l,temp=l-1;//tl维护l,temp是不断更新的该区间内这样的最大公约数的最大值 while(l>1;if(check(mid))l=mid+1,temp=mid;else r=mid-1;}return temp-tl+1;//返回这样的最大公约数的数量 }signed main(){cin>>a>>b>>k;ans=halfMaxNum(1,a-1)+halfMaxNum(a,b);//将这两个区间的这样的最大公约数的数量加起来即可 cout<<ans;    return 0;}