AcWing 4199. 公约数(试除法求约数返回vector+gcd求最大公约数+二分答案)
原题链接
中等
作者:
逸误
,
2024-04-04 16:08:37
,
所有人可见
,
阅读 26
//约数一定是gcd的约数,因此先求出gcd,再试除法求约数
//试除法求约数要点:1、i从1遍历到a/i即可;2、因此与之相对的那个要一块push进去!
//将所有约数排序后,用二分进一步优化,查找最大的x
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int a,b;
int q;
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
vector<int> get_divisors(int a)//试除法求约数
{
vector<int> res;//存答案
for(int i=1;i<=a/i;i++)//记住:这里i遍历到a/i即可!
{
if(a%i==0)
{
res.push_back(i);
if(i!=a/i)
res.push_back(a/i);//勿忘一次push一组!!
}
}
sort(res.begin(),res.end());//vector的排序语句!为了二分准备
return res;
}
int main()
{
cin>>a>>b;
int g=gcd(a,b);
auto ds=get_divisors(g);//从gcd中求出所有约数,返回容器ds
cin>>q;
while(q--)
{
//二分找出最大的x
int L,R;
scanf("%d%d",&L,&R);
int l=0,r=ds.size()-1;//希望res[mid]是最大的x
while(l<r)
{
int mid=l+r+1>>1;
if(ds[mid]>R)
r=mid-1;
else
l=mid;
}
//如此,就找到了最大的<R的x
if(ds[l]<L)
puts("-1");
else
printf("%d\n",ds[l]);
}
return 0;
}