二十五 4199. 公约数 (最大公约数|二分)

4199. 公约数 (最大公约数|二分)

思路：先用求最大公约数的模板求出a与b的最大公约数d，然后得到从1到d的全部公约数，最后利用二分法找到满足l≤x≤r条件的最大的公约数x。

import java.util.*;

public class Main {
    private static int a, b, q, l, r, cnt;
    private static int[] cds = new int[1350];
    
    private static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
    
    private static void init_divisors(int a, int b) {
        int d = gcd(a, b);
        cnt = 0;
        for (int i = 1; i <= d / i; i++) {
            if (d % i == 0) {
                cds[cnt++] = i;
                if (i != d / i) {
                    cds[cnt++] = d / i;
                }
            }
        }
        Arrays.sort(cds, 0, cnt);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        init_divisors(a, b);
        q = sc.nextInt();
        while(q-- > 0) {
            l = sc.nextInt();
            r = sc.nextInt();
            int left = 0, right = cnt - 1;
            while (left < right) {
                int mid = left + right + 1 >> 1;
                if (cds[mid] <= r) {
                    left = mid;
                }
                else {
                    right = mid - 1;
                }
            }
            if (cds[right] >= l) {
                System.out.println(cds[right]);
            }
            else {
                System.out.println(-1);
            }
        }
    }
}