扩展欧几里得算法是指对于两个数a,b

一定能找到x,y（均为整数，但不满足一定是正数）

满足x*a+y*b=gcd(a,b)

gcd（x,y)是指x 与 y的最大公约数

同余方程

a≡b(mod m) 等价于小学的运算式 b÷m 余数为a

也就是a mod m=b

乘法逆元

ax ≡  (mod m)

我们称 x 是 a 关于 m 的乘法逆元

可以等价于这样的表达式： a*x + m*y = 

 #include<cstdio>

 using namespace std;

 inline long long read()

 {

     long long x=,f=;char ch=getchar();

     while(ch<''||ch>'') {if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int a,b;

 void exgcd(int a,int b,int &x,int &y)

 {

     if(b==) {x=;y=;return;}

     exgcd(b,a%b,x,y);

     int t=x;x=y;y=t-a/b*y;

 }

 //ax ≡ 1 (mod b)

 //-> a*x + b*y = 1

 //->求出x和y后让x%b就是最小解了

 int main()

 {

     a=read();b=read();

     int x,y;

     exgcd(a,b,x,y);

     x=(x%b+b)%b;

     printf("%d",x);

     return ;

 }