POJ1576

首先明确一点$(\frac{A}{B}) \% 9973 \neq \frac{A\%9973}{B\%9973}$

但是$(\frac{A}{B}) \% 9973 = (A \times C)\%9973$，其中$C$是$B$关于$9973$的逆元，即$BC\equiv 1(mod\ 9973)$

根据乘法交换律得$(A\times C) \% 9973 = (C \times A) \% 9973 = (C \% 9973 \times A \% 9973) \% 9973$，由于题目已经给出了$n=A\%9973$，所以最终：

$$ (\frac{A}{B})\%9973 = (C\% 9973 \times n)\% 9973\ \ (BC\equiv 1 (mod\ 9973)) $$

import java.util.Scanner;

public class Main {
    static long x, y;
    static long exgcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long res = exgcd(b, a % b);
        long x1 = x;
        x = y;
        y = x1 - (a / b) * y;
        return res;
    }

    static long linearEquation(long a, long b, long m) throws Exception {
        long d = exgcd(a, b);
        if (m % d != 0)
            throw new Exception("Impossible");
        long n = m / d;
        x *= n;
        y *= n;
        return d;
    }
    
    static long inverseElement(long a, long b) throws Exception {
        long d = linearEquation(a, b, 1);
        x = (x % b + b) % b; // 保证x>0
        return d;
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        try {
            while ((T--) != 0) {
                int n = cin.nextInt();
                long b = cin.nextLong();
                inverseElement(b, 9973);
                System.out.println((x * n) % 9973);
            }
        } catch (Exception e) {
            System.out.println("Impossible");
        }
    }
}