算法1
gcd + 约数分解 + 二分
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10 ;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int cnt = 0 ;
int q[N] ;
void divide(int x){
for(int i=1;i<=x/i;i++)
if(x%i==0){
q[cnt++] = i ;
if(i!=x/i) q[cnt++] = x / i ;
}
sort(q,q+cnt) ;
}
int main()
{
int a , b ; cin >> a >> b ;
divide(gcd(a,b)) ;
int T ; cin >> T ;
while(T--){
int x , y ; cin >> x >> y ;
int l = -1 , r = cnt ;
while(l + 1 < r){ // 双开区间二分,找到最大的满足条件的值
int mid = l+r>> 1 ;
if(q[mid]<=y) l = mid ;
else r = mid ;
}
if(q[l]>=x) cout << q[l] << endl ;
else cout << -1 << endl ;
}
}