AcWing 4199. 公约数
原题链接
中等
作者:
木可柯
,
2024-04-10 16:41:26
,
所有人可见
,
阅读 5
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long LL;
vector<LL> s;
LL a, b, q;
void getyinzi(LL a, LL b)
{
//求出两个数的最大公因数
LL g = __gcd(a, b);
for(int i = 1; i <= g / i; i++)
{
//如果g能被i整除,说明i也能整数a和b
if(g % i == 0){
s.push_back(i);
if(g / i != i) s.push_back(g / i);
}
}
//从小打到拍个序
sort(s.begin(), s.end());
// for(auto item : s)
// cout << item << " ";
}
int main()
{
cin >> a >> b >> q;
getyinzi(a, b);
while(q--) {
LL l, r;
cin >> l >> r;
bool flge = 1;
for(LL i = s.size() - 1; i >= 0;i--) {
//如果最大的因子小于等于r并且大于等于l说明是合法的直接输出并退出循环
if(s[i] >= l && s[i] <= r) {
cout << s[i] << endl, flge = 0;
break;
}
}
if(flge) cout << -1 << endl;
}
return 0;
}