exgcd模板

逆元模板P1082

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 int exgcd(int a, int b, int &x, int &y) {
 5     if(!b) {
 6         x = 1;
 7         y = 0;
 8         return a;
 9     }
10     int g = exgcd(b, a % b, x, y);
11     std::swap(x, y);
12     y -= (a / b) * x;
13     return g;
14 }
15 
16 int main() {
17     int a, b;
18     scanf("%d%d", &a, &b);
19     int x, y;
20     exgcd(a, b, x, y);
21     x = (x % b + b) % b;
22     printf("%d", x);
23     return 0;
24 }

exgcd

注意exgcd不仅可以求解ax+by=gcd，还可以直接求解

ax+by=c(gcd|c)

代码：

 1 LL Val;
 2 LL mygcd(LL a, LL b, LL &x, LL &y) {
 3     if(!b) {
 4         x = Val / a;
 5         y = 0;
 6         return a;
 7     }
 8     LL g = mygcd(b, a % b, x, y);
 9     std::swap(x, y);
10     y -= (a / b) * x;
11     return g;
12 }

mygcd

但是有个缺点，就是跟上面比起来可能会爆long long而出错(屠龙勇士)

关于exgcd的推导过程：