算法基础-扩展欧几里得算法

扩展欧几里得

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            int[] m = exgcd(a, b);
            System.out.println(m[0] + " " + m[1]);
        }
    }
    private static int[] exgcd(int a, int b) {
        if (b == 0)
            return new int[]{1, 0};
        int[] result = exgcd(b, a % b);
        int x = result[0];
        int y = result[1];
        result[0] = y;
        result[1] = x - (a / b) * y;
        return result;
    }
}

线性同余方程

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            int m = in.nextInt();
            int[] r = exgcd(a, m);
            if(b % r[2] != 0) {
                System.out.println("impossible");
            } else {
                System.out.println(r[0] * ((long) b / r[2]) % m);
            }
        }
    }

    private static int[] exgcd(int a, int m) {
        if (m == 0)
            return new int[]{1, 0, a};
        int[] result = exgcd(m, a % m);
        int x = result[0];
        int y = result[1];
        result[0] = y;
        result[1] = x - (a / m) * y;
        return result;
    }
}