AcWing 4199. 公约数
原题链接
中等
作者:
小周不会做题
,
2024-04-09 17:02:10
,
所有人可见
,
阅读 3
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int aa[N];
int main()
{
int a,b,q;
scanf("%d%d",&a,&b);
int t=__gcd(a,b);
int cnt=1;
for(int i=1;i<=t/i;i++) //在O^(0.5)时间内求出a,b最大公约数的所有约数
{
if(t%i==0&&i*i!=t)
{
aa[cnt++]=i;
aa[cnt++]=t/i;
}
if(i*i==t)
{
aa[cnt++]=i;
}
}
sort(aa+1,aa+cnt+1);
scanf("%d",&q);
while(q--)
{
int l,r;
bool tt=false;
scanf("%d%d",&l,&r);
for(int i=cnt;i>=1;i--)
{
if(aa[i]>=l&&aa[i]<=r) //从大到小判断aa[i]是否在l-r之间
{
cout<<aa[i]<<endl;
tt=true;
break;
}
}
if(!tt) cout<<-1<<endl;
}
return 0;
}