//package adrui;import java.util.*;public class Main{ public static void main(String...args){ Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t-- > 0){ long m = in.nextLong(), n = in.nextLong(); long ans = expgcd(m, n); String tmp = "YES"; if(ans == 1) tmp = "NO"; System.out.PRintln(tmp); } in.close(); } public static long expgcd(long a, long b){ if（b == 0）{ return a; } return expgcd(b, a % b); }}
HDU 1576
链接：HDU 1576
题解
推一下式子就成， 注意B的系数要取反
code
//package adrui;import java.util.*;public class Main{ static long c; public static void main(String...args){ Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t-- > 0){ c = in.nextLong(); long[] x = new long[1];/**数组实现引用*/ long[] y = new long[1]; long n = in.nextLong(); expgcd(9973, n, x, y); y[0] = -y[0]; long ans = y[0] % 9973; if(ans < 0) ans += 9973; System.out.println(ans); } in.close(); } public static void expgcd(long a, long b, long[] x, long[] y){ if(b == 0){ x[0] = -c; y[0] = 0; return; } expgcd(b, a % b, y, x); y[0] -= a / b * x[0]; }}
/** *@author : adrui */import static java.lang.System.*;import java.util.*;public class Main{ static boolean f;/**静态全局*/ public static void main(String...args){ Scanner in = new Scanner(System.in); while(in.hasNext()){ f = false; int a = in.nextInt(), b = in.nextInt(); int[] x = new int[1]; int[] y = new int[1]; expgcd(a, b, x, y); if(!f) out.println("sorry"); else{ int ans = x[0] % b; if(ans < 0) ans += b;/** b = b / gcd(a, b) */ out.println(ans + " " + (1 - (long)ans * a) / b);/** ans * a 可能会爆int， 用通解也可以*/ } } } public static void expgcd(int a, int b, int[] x, int[] y){ if(b == 0){ if(a == 1) { x[0] = 1; y[0] = 0; f = true;/**有解标记*/ } return; } expgcd(b, a % b, y, x); y[0] -= a / b * x[0]; }}
HDU 2504
链接 ： HDU 2504
裸题
code
/** *@author : adrui */import static java.lang.System.*;import java.util.*;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(), b = in.nextInt(); for(int i = b + b; ; i += b){ if(expgcd(a, i) == b){ out.println(i); break; } } } } public static int expgcd(int a, int b){ if(b == 0){ return a; } return expgcd(b, a % b); }}
