CF75C Modified GCD

本文主要是介绍CF75C Modified GCD，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题,貌似无从下手QAQ

但是很简单就可以想到二分吧,正好二分能过QAQ

自然就是先跑一个gcd~~(想必大家都会了)~~

然后…

然后就是一个二分呀QAQ

上代码

#include<bits/stdc++.h>
using namespace std;
int A,B,N,number=0;
int divisor[10000];
int gcd(int x,int y)//gcd
{if(y==0)return x;return gcd(y,x%y);
}
void solve()
{int low,high;scanf("%d%d",&low,&high);//每次查询的区间int _left=1,_right=number,middle,answer=-1;while(_left<=_right)//二分{middle=(_left+_right)/2;//取midif(divisor[middle]>high/*判断是大了还是小了*/)_right=middle-1;else{_left=middle+1;if(divisor[middle]>=low)answer=divisor[middle];//记录下答案}}printf("%d\n",answer);//输出answer
}
int main()
{scanf("%d%d",&A,&B);int num=gcd(A,B);//记录下gcd后的值int Max=(int)(sqrt(num)),i;for(i=1;i<=Max;i++)if(num%i==0)//取出因数{divisor[++number]=i;divisor[++number]=num/i;}sort(divisor+1,divisor+number+1);//排一下序,符合单调性scanf("%d",&N);for(i=1;i<=N;i++)solve();//解决问题QAQ
}

然后
…
就
…
过了…

这篇关于CF75C Modified GCD的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---