[HDU1576] A/B（扩展欧几里得）

传送门

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

上一篇：[luoguP1186] 玛丽卡（spfa）

下一篇：[luoguP2801] 教主的魔法（二分 + 分块）

---

数论 扩展欧几里得