题目描述
给定两个正整数 a 和 b。
你需要回答 q 个询问。
每个询问给定两个整数 l,r
你需要找到最大的整数 x,满足:
1.x是 a 和 b 的公约数。
2.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
输出样例:
3
-1
9
算法1
(暴力枚举) $O(n^2)$
C++ 代码
include[HTML_REMOVED]
using namespace std;
int gcd(int a,int b){
return b ? gcd(b,a%b) : a;
}
int main(){
int a,b;
cin>>a>>b;
int x;
x=gcd(a,b);
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
if(x>=l && x<=r) cout<<x<<endl;
else if(x < l) cout<<"-1"<<endl;
else if(x > r){
while(a % r !=0 || b % r != 0){
r--;
}
if(r>=l) cout<<r<<endl;
else cout<<"-1"<<endl;
}
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla