题目描述

最大公约数+试除法求约数+二分

样例

import java.util.*;

public class Main {

    static final int N = 1350;
    static int[] q = new int[N];
    //统计a,b公约数的数量
    static int cnt;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        initDivisors(a, b);

        int n = scanner.nextInt();
        while (n-- > 0) {
            int L = scanner.nextInt();
            int R = scanner.nextInt();

            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;
            }

            //符合条件才输出 不符合输出-1
            if (q[r] >= L) System.out.println(q[r]);
            else System.out.println("-1");
        }
    }

    //求a,b的最大公约数
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    //对于a,b的最大公约数去求它的每一个约数，也是a，b的每一个公约数
    static void initDivisors(int a, int b) {
        int d = gcd(a, b);

        for (int i = 1; i <= d / i; i++) {
            if (d % i == 0) {
                q[cnt++] = i;
                //这里特判一下，因为约数有可能是两个约数相同，比如4*4,5*5,它本只有一个约数，所以就要特判一下
                if (i != d / i) q[cnt++] = d / i;
            }
        }

        //把这些公约数排序
        Arrays.sort(q, 0, cnt);
    }
}