蓝桥杯刷题--python-36

4199. 公约数 - AcWing题库

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

def init_divisors(a,b):
    d=gcd(a,b)
    i=1
    
    while i*i<=d:
        if d%i==0:
            ans.append(i)
            if i!=d//i:ans.append(d//i)
        i+=1
    ans.sort()

a,b=map(int,input().split())
ans=[]
init_divisors(a,b)
q=int(input())
for _ in range(q):
    L,R=map(int,input().split())
    l=0;r=len(ans)-1
    while (l<r):
        mid=l+r+1>>1
        if ans[mid]<=R:l=mid
        else: r=mid-1
    if ans[r]>=L:
        print(ans[r])
    else:
        print("-1")