同余表示两个数模上另一个数相同；写作ax=b(mod p)，
我们把ax=1(MOD P) x称为a在p的逆元；
求逆元就是求同余方程
求同余方程使用扩展欧几里得法
1 int exgcd(int a, int b, int& x, int& y) { 2 if (b == 0) { 3 x = 1; 4 y = 0; 5 return a; 6 } 7 int d = exgcd(a, b, y, x); 8 y -= (a / b) * x; 9 return d; 10 }//返回的d表示a与b的最大公因数，x,y就是同余方程ax+yp=b的最小解；
x=x0+p/gcd(a,p);
y=y0+a/gcd(b,p);
x=(x+b/d)%b/d;
如果b不是d的倍数那么就不成立，成立要乘以b/d;
feishu定理：如果gcd(a,b)=d;
那么ax+by一定是d的倍数，存在x，y使得ax+by=d；
