题目描述
给定两个正整数 a
和 b
。
你需要回答 q
个询问。
每个询问给定两个整数 l,r
,你需要找到最大的整数 x
,满足:
x
是 a
和 b
的公约数。
l≤x≤r
。
输入格式
第一行包含两个整数 a,b
。
第二行包含一个整数 q
。
接下来 q
行,每行包含两个整数 l,r
。
输出格式
每个询问输出一行答案,即满足条件的最大的 x
,如果询问无解,则输出 −1
。
数据范围
前六个测试点满足 1≤a,b≤100
,1≤q≤20
。
所有测试点满足 1≤a,b≤109
,1≤q≤104
,1≤l≤r≤109
。
样例
9 27
3
1 5
10 11
9 11
算法
从大到小枚举最大公约数的因数就可以了
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
vector<LL>v;
int main()
{
LL a, b;
scanf("%lld%lld", &a, &b);
int n;
scanf("%d", &n);
int d = gcd(a, b);
for(LL t = 1; t <= sqrt(d); t ++) //获取最大公约数的因数
if(d % t == 0)
v.push_back(t), v.push_back(d / t);
sort(v.begin(), v.end()); //排序
while(n --)
{
LL l, r;
bool jud = false; //判断是否输出,没有输出最后输出-1
scanf("%lld%lld", &l, &r);
for(LL t = v.size() - 1; t >= 0; t --) //从大到小枚举
if(v[t] >= l && v[t] <= r) //符合就输出
{
jud = true;
cout << v[t] << endl;
break;
}
if(!jud)cout << "-1" << endl;
}
return 0;
}