逆元模板P1082

1 #include 
      
        2 #include 
       
         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不仅可以求解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 }

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

关于exgcd的推导过程：