对于两两互质的一组整数，对于一组整数有，则可以唯一地确定一个在内的解使得此同余方程组成立。
方法：考虑两个方程的情况：即n%m1 = a，n%m2 = b，显然如果不在模意义下的话，那么a+(b-a)显然可以成为第二个方程的解，然而b-a的偏移量不满足模意义，我们可以求出m1关于m2的逆元w，则显然a+(b-a)m1w可以成为方程的解。
按照这种构造方法，同理，我们可以关于m1，m2，......,mn进行类似的构造，即可得出方程组的解。
POJ 1006
#include <cstdio> #include <stack> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #include <map> #include <vector> #include <queue> #include <set> #define eps 1e-8 typedef long long ll; const double PI = acos(-1.0); const int maxn = 1e6; const int INF = 0x3f3f3f; const ll linf = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; using namespace std; int a[maxn],m[maxn]; int n; int exgcd(int a, int b, int &x, int &y) { if(!b) { x = 1; y = 0; return a; } int d = exgcd(b,a%b,x,y); int z = x; x = y; y = z - (a/b)*y; return d; } int CRT() { int M = 1,ans = 0; int x,y; n = 3; for(int i = 0; i<n; i++) M *= m[i]; for(int i = 0; i<n; i++) { int Mi = M/m[i]; exgcd(Mi,m[i],x,y); ans = (ans+a[i]*Mi*x)%M; } ans = (ans+M)%M; return ans; } int main() { ios::sync_with_stdio(false); m[0] = 23; m[1] = 28; m[2] = 33; int p,e,i,d; int cnt = 0; while(cin>>p>>e>>i>>d) { if(p+e+i+d == -4) break; a[0] = p; a[1] = e; a[2] = i; int ans = CRT(); if(ans <= d) ans += 21252; cout<<"Case "<<++cnt<<": the next triple peak occurs in "<<ans-d<<" days."<<endl; } return 0; }当mi不一定满足两两互质的条件时，则中国剩余定理不再适用。可以考虑使用数学归纳法，假设已急求出了前k-1个方程构成的方程组的一个解x。记，则x+t*m是前k个方程的通解。
所以，只需考虑第k个方程，即求出一个整数t，使得，该方程等价于即可。若有解，则x' = x+t*m就是前k个方程构成的方程组的一个解。
HDU 3579
#include <cstdio> #include <stack> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #include <map> #include <vector> #include <queue> #include <set> #define eps 1e-8 typedef long long ll; const double PI = acos(-1.0); const int maxn = 1e6; const int INF = 0x3f3f3f; const ll linf = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; using namespace std; ll a[maxn],m[maxn]; int n; ll gcd(ll a, ll b) { return b==0?a:gcd(b,a%b); } ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) { x = 1; y = 0; return a; } ll d = exgcd(b,a%b,x,y); ll z = x; x = y; y = z-(a/b)*y; return d; } ll exCRT() { ll lcm = 1; for(int i = 0; i<n; i++) lcm = m[i]/gcd(m[i],lcm)*lcm; for(int i = 1; i<n; i++) { ll A = m[0],B = m[i],C = a[i]-a[0]; ll x,y; ll d = exgcd(A,B,x,y); if(C%d) return -1; ll Mod = m[i]/d; ll K = ((x*C/d)%Mod+Mod)%Mod; a[0] += m[0]*K; m[0] *= m[i]/d; } if(!a[0]) return lcm; return a[0]; } int main() { //ios::sync_with_stdio(false); int T; cin>>T; int tt = 1; while(T--) { cin>>n; for(int i = 0; i<n; i++) cin>>m[i]; for(int i = 0; i<n; i++) cin>>a[i]; ll ans = exCRT(); printf ("Case %d: ",tt++); cout<<ans<<endl; } return 0; }POJ 2891
/** **/ #include <cstdio> #include <stack> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #include <map> #include <vector> #include <queue> #include <set> #define eps 1e-8 typedef long long ll; const double PI = acos(-1.0); const int maxn = 1e6; const int INF = 0x3f3f3f; const ll linf = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; using namespace std; ll a[maxn],m[maxn]; int n; ll gcd(ll a, ll b) { return b==0?a:gcd(b,a%b); } ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) { x = 1; y = 0; return a; } ll d = exgcd(b,a%b,x,y); ll z = x; x = y; y = z-(a/b)*y; return d; } ll exCRT() { ll lcm = 1; for(int i = 0; i<n; i++) lcm = m[i]/gcd(m[i],lcm)*lcm; for(int i = 1; i<n; i++) { ll A = m[0],B = m[i],C = a[i]-a[0]; ll x,y; ll d = exgcd(A,B,x,y); if(C%d) return -1; ll Mod = m[i]/d; ll K = ((x*C/d)%Mod+Mod)%Mod; a[0] += m[0]*K; m[0] *= m[i]/d; } if(!a[0]) return lcm; return a[0]; } int main() { //ios::sync_with_stdio(false); while(cin>>n) { for(int i = 0; i<n; i++) cin>>m[i]>>a[i]; ll ans = exCRT(); cout<<ans<<endl; } return 0; }HDU 1788
/** **/ #include <cstdio> #include <stack> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #include <map> #include <vector> #include <queue> #include <set> #define eps 1e-8 typedef long long ll; const double PI = acos(-1.0); const int maxn = 1e6; const int INF = 0x3f3f3f; const ll linf = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; using namespace std; int n; ll gcd(ll a, ll b) { return b==0?a:gcd(b,a%b); } ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } int main() { ios::sync_with_stdio(false); int n,a; while(cin>>n>>a && n+a) { ll ans = 1; for(int i = 0; i<n; i++) { ll m; cin>>m; ans = lcm(m,ans); } cout<<ans-a<<endl; } return 0; }HDU 1573
/** **/ #include <cstdio> #include <stack> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #include <map> #include <vector> #include <queue> #include <set> #define eps 1e-8 typedef long long ll; const double PI = acos(-1.0); const int maxn = 1e6; const int INF = 0x3f3f3f; const ll linf = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; using namespace std; ll a[maxn],m[maxn]; int n; ll M; ll gcd(ll a, ll b) { return b==0?a:gcd(b,a%b); } ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) { x = 1; y = 0; return a; } ll d = exgcd(b,a%b,x,y); ll z = x; x = y; y = z-(a/b)*y; return d; } ll exCRT() { ll lcm = 1; for(int i = 0; i<n; i++) lcm = m[i]/gcd(m[i],lcm)*lcm; for(int i = 1; i<n; i++) { ll A = m[0],B = m[i],C = a[i]-a[0]; ll x,y; ll d = exgcd(A,B,x,y); if(C%d) return -1; ll Mod = m[i]/d; ll K = ((x*C/d)%Mod+Mod)%Mod; a[0] += m[0]*K; m[0] *= m[i]/d; } if(!a[0]) return lcm; return a[0]; } int main() { ios::sync_with_stdio(false); int T; cin>>T; int tt = 1; while(T--) { cin>>M>>n; for(int i = 0; i<n; i++) cin>>m[i]; ll lcm = 1; for(int i = 0; i<n; i++) lcm = m[i]/gcd(m[i],lcm)*lcm; for(int i = 0; i<n; i++) cin>>a[i]; ll ans = exCRT(); if(ans == -1 || ans>M) { cout<<0<<endl; continue; } cout<<(M-ans)/lcm+1<<endl; } return 0; }
