问题描述：求出方程组x≡a[i](mod m[i])的解x（其中要求m[0],m[1]……m[n-1]两两互质）

问题证明：
中国剩余定理给出了以下的一元线性同余方程组：
 
中国剩余定理说明：假设整数 m1, m2, ... , mn两两互质，则对任意的整数： a1, a2, ... , an，
方程组(S)有解，并且通解可以用如下方式构造得到：
设
 
是整数 m1, m2, ... , mn的乘积，并设
 
是除了 mi以外的 n- 1个整数的乘积。
设
 
这个就是逆元了
   
通解形式为
   
在模M的意义下，方程组(S) 只有一个解：
 


结论：

1.对于解x，要求m两两互质

2.解x=∑(M[i]*M[i]逆*a[i]) 其中逆元用扩展GCD求，不能用费马，因为a,p不一定互质

3.注意下LL


例题：POJ 1006

题意：

x≡p(mod 23)

x≡e(mod 28)

x≡i(mod 33)

中国剩余定理裸题，如果会了中国剩余定理，难易程度和A+B一样

#include<cstdio> #include<iostream> #define PI acos(-1.0) #define pb push_back #define F first #define S second #define debug puts using namespace std; typedef long long ll; const int N=5e3+5; const int MOD=1e9+7; const int INF=0x3f3f3f3f; void ext_gcd(int a,int b,int&x,int&y,int d){ if(!b) x=1,y=0,d=a; else{ ext_gcd(b,a%b,y,x,d); y-=x*(a/b); } } int CRT(int a[],int m[],int n){ int M=1,res=0; for(int i=0;i<n;++i) M*=m[i]; for(int i=0;i<n;i++){ 复杂度O(n/*log2(max(m[i],M/m[i]))) int x,y,d; ext_gcd(M/m[i],m[i],x,y,d); res=(res+a[i]*M/m[i]*x)%M; } return ((res%M)+M)%M; } int main(void){ int e,p,i,d,ks=0; while(cin>>e>>p>>i>>d){ if(e==-1) break; int m[4]={23,28,33}; int a[4]; a[0]=e,a[1]=p,a[2]=i; int ans=((CRT(a,m,3)-d)%21252+21252)%21252; if(!ans) ans=21252; printf("Case %d: the next triple peak occurs in %d days.\n",++ks,ans); } return 0; }