哈希表求公约数
利用哈希表求得两数公约数,然后排序,从大到小遍历每一个数,如果这个公约数在给定区间范围内,则该数就是在这个区间内最大公约数。
C++ 代码
#include<iostream>
#include<cstdio>
#include<unordered_set>
#include<vector>
#include<algorithm>
using namespace std;
unordered_set<int> s;
vector<int> A;
int x,y;
int main(void)
{
scanf("%d%d",&x,&y);
for(int i=1;i<=x/i;i++)
{
if(x%i==0)
s.insert(i),s.insert(x/i);
}
for(int i=1;i<=y/i;i++)
{
if(y%i==0)
{
if(s.count(i))
A.push_back(i);
if(s.count(y/i))
A.push_back(y/i);
}
}
int m;
scanf("%d",&m);
sort(A.begin(),A.end());
while(m--)
{
int l,r,cot=1;
scanf("%d%d",&l,&r);
for(int i=A.size()-1;i>=0;i--)
if(A[i]>=l&&A[i]<=r)
{
printf("%d\n",A[i]);
cot=0;
break;
}
if(cot)
printf("-1\n");
}
return 0;
}