A/B涉及同余定理+逆元（除法逆元）

同余定理：
数论中的关键概念。对于任意一个正整数m，若存在两个整数a与b，使得a减去b的结果可以被m整除，即(a - b)除以m的商为整数，则称a与b在模m下同余，记作a≡b\ (\ mod\; m)。模m下的同余关系构成了整数集合上的等价关系

设

因此

需要计算(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

设m=9973则

即

因此

已知 \;B\; 的具体数值后，可通过扩展欧几里得算法求得 \;C\; 的值，从而得出最终结果

依据费马小定理可推导出以下结论：

因此

代码:

    #include