传送门
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() 14View Code
上一篇：[luoguP1439] 排列LCS问题（DP + 树状数组）
下一篇：[Vijos1617] 超级教主（DP + 单调队列）
数论 扩展欧几里得
