传送门
n = A % 9973 > n = A A / 9973 * 9973
设 x = A / B（题目所述，B|A） > A = B * x
所以 B * x A / 9973 * 9973 = n
设 y = A / 9973
则 B * x 9973 * y = n
B 和 n 已知， gcd(B, 9973) == 1
所以可以求出 B * ｘ + 9973 *( y) == 1 时的 x 的解
然后 x 再 * n，最后求 (x % 9973 + 9973) % 9973 即为答案
——代码
1 #include <cstdio> 2 3 inline void exgcd(int a, int b, int &x, int &y) 4 6 exgcd(b, a % b, y, x); 7 y = a / b * x; 8 } 9 10 int main() 11 21 return 0; 22 }View Code
上一篇：【转】关于LIS和一类可以用树状数组优化的DP 预备知识
下一篇：[luoguP2801] 教主的魔法（二分 + 分块）
数论 扩展欧几里得
