最近一直在学习数论，讲得很快，害怕落实的不好，所以做一道luogu的同余方程练练手。

 

关于x的同余方程

ax ≡ 1 mod m

那么x其实就是求a关于m的乘法逆元

ax + my = 1

对于这个不定方程的全部解是

{ x = x0 + m/gcd(a,m)

{ y = y0 - a/gcd(a,m)

我们可以用exgcd来求出其中的一组特解x0

那么什么是exgcd？

先不考虑exgcd，假设当前我们要处理的是求出 a 和 b的最大公约数，并求出 x 和 y 使得 a*x + b*y= gcd ，而我们已经求出了下一个状态：b 和 a%b 的最大公约数，并且求出了一组x1 和y1 使

得： b*x1 + (a%b)*y1 = gcd

那么我们看 a%b = （a-(a/b)*b）

所以

gcd = b*x1 + (a%b)*y1

= b*x1 + (a-(a/b)*b)*y1

= b*x1 + a*y1 – (a/b)*b*y1

= a*y1 + b*(x1 – a/b*y1)

那么我们对比前面一组 a*x + b*y = gcd

在这里 x = y1

y = x1 - a/b*y1

 

 

所以我们就可以递归来求exgcd了。

在gcd当中，gcd(a,b) = gcd(b,a%b)

 

那么exgcd的代码其实也多不了多少

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define ll long long 5 using namespace std; 6 ll a, b, x, y, k, ans; 7 int exgcd(ll a, ll b) 8 { 9     if(b == 0)10     {11         x = 1; y = 0;12         return a;13     }14     exgcd(b,a%b);15     k = x; 16     x = y; 17     y = k - a/b * y;18     return x;19 }20 int main()21 {22     cin>>a>>b;23     ans = exgcd(a,b);24     cout<<(ans+b)%b;25     return 0;26 }
       
      
     

 

其实你看gcd的代码这么短，肯定是背过的吧（#滑稽），exgcd也长不了多少，不行就背过吧（逃