[luoguP1082] 同余方程（扩展欧几里得）

传送门

ax≡1(mod b)

这个式子就是 a * x % b == 1 % b

相当于 a * x b * y == 1

只有当 gcd(a,b) == 1 时才有解，也就是说 ax + by = c 有解的充要条件是 c % gcd(a,b) == 0

一般，我们能够找到无数组解满足条件，但是一般是让你求解出最小的那个正整数解

即为 (x % b + b) % b)，+b是为了保证不为负数

可以这样想 a * x % b == 1 % b

　　　 > a * x % b == 1

　　　 > (a * x % b) % b == 1

求 x 最小正整数，那么直接取膜就好。

——代码

1 #include <cstdio> 2 3 int a, b, x, y, gcd; 4 5 inline int exgcd(int a, int b, int &x, int &y) 6 8 int r = exgcd(b, a % b, y, x); 9 y = a / b * x; 10 return r; 11 } 12 13 int main() 14
View Code

上一篇：[luoguP1027] Car的旅行路线（Floyd）

下一篇：[Vijos1617] 超级教主（DP + 单调队列）

---

数论 扩展欧几里得