設(shè)m1,m2,...,mk是兩兩互素的正整數(shù)，對(duì)于任意的正整數(shù)a1,a2,a3,..,ak 同余方程組：
x≡a1 （mod m1）
x≡a2 （mod m2）
...
x≡ak （mod mk)
必有解， 且解可寫為
x≡M1N1a1+MkNkak+....MkNkak (mod m)
其中 m=m1m2m3....mk
Mi=m/mi,(1<=i<=k)
Nj滿足MjNj≡1(mod mj),1<=j<=k
即：
Ni,Mi是對(duì)模mi的互為逆元。
http://www.cnblogs.com/walker01/archive/2010/01/23/1654880.html
這篇寫得不錯(cuò)哇。
中國(guó)剩余定理O(nlogn),還算高效率的。
#include<stdio.h>
#include<string.h>
#include<math.h>
int a[25],m[25],M[25],N[25];
int gcd_ext(int a,int b,int *x,int *y)
{
int d,tmp;
if (b==0)
{
*x=1;*y=0;
return a;
}
d=gcd_ext(b,a%b,x,y);
tmp=*x;*x=*y;*y=tmp-(a/b)**y;
return d;
}
long long ChReTheorim(int n)
{
int i,x,y;
long long ans,mul;
mul=1;
for (i=1;i<=n ;i++ )
mul*=m[i];
ans=0;
for (i=1;i<=n ;i++ )
{
M[i]=mul/m[i];
gcd_ext(M[i],m[i],&x,&y);
N[i]=(x+m[i])%m[i];
ans=(ans+a[i]*M[i]*N[i]) % mul;
}
return ans;
}
int main()
{
int i,n;
long long ans;
while (scanf("%d",&n)==1)
{
mul=1;
for (i=1;i<=n ;i++ )
scanf("%d%d",&a[i],&m[i]);
ans=ChReTheorim(n);
printf("%lld\n",ans);
}
return 0;
}
尼瑪，看算法上的乘法逆元給看成加法逆元了。我還以為我找到O（n）的算法呢。氣死：
a=a1(mod n1)
a=a2(mod n2)
則
a=(a1*n2*N2+a2*n1*N1) % (n1*n2)
其中
N1是n1模n2的逆元，N2是n2模n1的逆元。
如此反復(fù)迭代，可求解。
long long TongYu(int a1,int n1,int a2,int n2)
{
int N1,N2,x,y,ans;
gcd_ext(n1,n2,&x,&y);
N1=(n2+x) % n2;
gcd_ext(n2,n1,&x,&y);
N2=(n1+x) % n1;
printf("%d %d\n",N1,N2);
ans=(a1*n2*N2+a2*n1*N1) % (n1*n2);
return ans;
}
哦，