扩展欧几里得
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;}
}
