数论:同余，逆元，求同余方程，翡蜀定理

同余表示两个数模上另一个数相同；写作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；