逆元

什么是逆元
对于a再（modP）下
如果有a*X%P=1则我们称a的逆元为X（即a−1）
显然a*（a−1 ）=1；
逆元的求法
<1>使用拓展欧几里得。
int exgcd(int a,int b,int &X,int &Y){ if(!b){X=1,Y=0;return a;} int t=x-(a/b)*y; return exgcd(b,a%b,y,t); } <2> O(n)求1~n逆元表 为了求i的逆元
我们设 r=P%i，k=P/i;
r+k*i=0
两边同时乘以 i−1 和b−1 得
k*r−1 +i−1 =0
即 i−1 =-k*r−1
即i−1 =-P/i*(P%i)−1 那么可以从2递推到n求逆元，在求i之前p%i一定已经求出
这样就可以O(n)求出所有逆元了
(初始化 1−1=1) inv[1]=1; for(int i=2;i<=n;i++) inv[i]=1ll*(P-P/i)*inv[P%i]%P;

中国剩余定理

给出一系列同余的式子，求x的解：
保证a1,a2,a3…an两两互质 我们发现，
<1>如果二数不能整除，若被除数扩大n倍，而除数不变，则其余数也同时扩大相同的倍数（小于除数）。
<2>几个数相加，如果只有一个数，不能被数m整除，而其他加数均能被数a整除，那么余数即为其对于m的余数。
我们设M=∏ni=1ai；
于是我们可以这样构造对于每个ai我们求出对应的Mi(Mi=M/ai) 我们发现对于每一个M−1i * Mi * ai % mi一定对于ai
有由于其他数都为Mi的因子所以可以不要考虑了
于是我们得到x=∑ni=1M−1i * Mi * ai %M 举个例子x%3 == 2，x%5 == 3，x%7 == 2,求x 的值 a*15(3 * 5)%7 == 1;
b*21(3 * 7)%5 == 1;
c*35(7 * 5)%3 == 1;
可求得a,b,c的值为1,1,2;（即逆元）
我们可得15%7 == 1 , 21%5 == 1 , 70%3 == 1；
Ans = (15*2 + 21*3 + 70*2) % lcm(3,5,7);
Ans = 23; int CRT(int a[],int m[],int n) { int M=1,ans=0; for(int i=1;i<=n;i++)M*=m[i]; for(int i=1,x, y;i<=n;i++){ int Mi=M/m[i]; exgcd(Mi,m[i],x,y); ans=(ans+Mi*x*a[i])%M; } if(ans<0)ans+=M; return ans; }