A/B
HDU - 1576
要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2 1000 53 87 123456789
Sample Output
7922 6060
import java.util.*;import static java.lang.Math.abs;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();while(t>0){int n = sc.nextInt();int b = sc.nextInt();long res = Ext_Gcd.outPut(n,b);System.out.println(res);t--;}}private static class Ext_Gcd{static long x;static long y;public static long outPut(long n,long b){try {long d = lineE(b,9973,1);b = 9973;b/=d;x = (x%b+b)%b;return n*x%9973;}catch (Exception e){System.out.println("无解");}return 0;}public static long lineE(long a,long b,long m)throws Exception{long d = ext_Gcd(a,b);if(m%d != 0){throw new Exception("无解");}long n = m/d;x *=n;y *=n;return d;}public static long ext_Gcd(long a,long b){if(b == 0){x = 1;y = 0;return a;}long res = ext_Gcd(b,a%b);long x1 = x;x = y;y = x1-a/b*y;return res;}}
}