给定两个正整数 $a$ 和 $b$。
你需要回答 $q$ 个询问。
每个询问给定两个整数 $l,r$,你需要找到最大的整数 $x$,满足:
- $x$ 是 $a$ 和 $b$ 的公约数。
- $l \le x \le r$。
输入格式
第一行包含两个整数 $a,b$。
第二行包含一个整数 $q$。
接下来 $q$ 行,每行包含两个整数 $l,r$。
输出格式
每个询问输出一行答案,即满足条件的最大的 $x$,如果询问无解,则输出 $-1$。
数据范围
前六个测试点满足 $1 \le a,b \le 100$,$1 \le q \le 20$。
所有测试点满足 $1 \le a,b \le 10^9$,$1 \le q \le 10^4$,$1 \le l \le r \le 10^9$。
输入样例:
9 27
3
1 5
10 11
9 11
输出样例:
3
-1
9
算法1
(数学+二分) $O(n^2)$
于是我们可以通过枚举 $(a,b)$ 的所有约数来确定答案 $x$。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1350;
int q[N],cnt;
int gcd(int a,int b){
return b ? gcd(b,a % b) : a;
}
void init_divisors(int a,int b){
int d = gcd(a,b);
for(int i = 1;i <= d / i;i ++){
if(d % i == 0){
q[cnt ++] = i;
if(i != d / i) q[cnt ++] = d / i;
}
}
sort(q,q + cnt);
}
int main(){
int a,b;
scanf("%d%d",&a,&b);
init_divisors(a,b);
int n;
scanf("%d",&n);
while(n --){
int L,R;
scanf("%d%d",&L,&R);
int l = 0,r = cnt - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(q[mid] <= R) l = mid;
else r = mid - 1;
}
if(q[r] >= L) printf("%d\n",q[r]);
else puts("-1");
}
return 0;
}