孙子定理 互质与非互质

2019-04-14 17:44发布

站内文章 / 模拟电子
10201 0 1646

互质


 输入 ： x = ai （mod ni） (i=1,2...,k)
令： n=n1*n2*.....*nk; mi=n/ni; ci=mi(mi^ -1 mod ni) ans=(a1*c1+a2*c2+......+ak*ck)(mod n)




非互质


结论：  x = a1 （mod n1） x = a2 （mod n2） --> x= a     ( mod  n) 其中a=a1+n1*K；(K为n1k1=a2-a1(mod n2)最小非负解) n=lcm（n1,n2）；
证明：
Res = a1+n1*k1 ① 
Res = a2+n2*k2 
即 a1+n1*k1 = a2+n2*k2 

令d = gcd (n1, n2)  左右2边同时除以d并整理得

n1*k1/d – (a2-a1)/d = n2*k2/d = (n2/d)*k2 
∴有 n1*k1/d – (a2-a1)/d = 0 (mod n2/d)         n1*k1 = (a2-a1) (mod n2/d) 

易知k1有多个解 设K`为k1的解，必然存在最小非负整数K` 使得得 k1 = K` (mod n2/d) ③ 
即k1 = K` + (n2/d)*C ② (设C为某一整数) 

②代入①得
Res = a1 + n1*( K` + (n2/d)*C)         Res = a1 + n1*K` + (n1*n2/d)*C 
即Res – (a1+n1*K`) = 0 (mod (n1*n2/d)) 

 Res = (a1+n1*K`) (mod (n1*n2/d)) 
//poj1006 #include #include typedef int ll; using namespace std; const int n[]={0,23,28,33}; const int m[]={0,924,759,644}; int m1[4]; int c[4]; const int nn=21252; struct sol{ ll x,y,d; sol(ll xx=0,ll yy=0,ll dd=0){ x=xx; y=yy; d=dd; } }; inline sol gcd(ll a,ll b) { if (b==0) return sol(1,0,a); sol temp=gcd(b,a%b); ll x1=temp.x,y1=temp.y,d1=temp.d; return sol(y1,x1-a/b*y1,d1); } int p,e,k,start,cas=0; int ans; int main() { freopen("t.in","r",stdin); freopen("t.out","w",stdout); for (int i=1;i<=3;i++) m1[i]=gcd(m[i],n[i]).x; for (int i=1;i<=3;i++) c[i]=m[i]*((m1[i]%n[i]+n[i])%n[i]); while (scanf("%d%d%d%d",&p,&e,&k,&start)) { if (p==-1 && e==-1 && k==-1 && start==-1) break; ans=(p*c[1]+e*c[2]+k*c[3]-start)%nn; ans=(ans%nn+nn-1)%nn+1; printf("Case %d: the next triple peak occurs in %d days. ",++cas,ans); } return 0; }
//poj2891 #include #include #include #define cl(x) memset(x,0,sizeof(x)) typedef __int64 ll; inline ll gcd(ll a,ll b,ll& x,ll& y) { if (b==0) { x=1; y=0; return a; } ll temp,d=gcd(b,a%b,x,y); temp=x; x=y; y=temp-a/b*y; return d; } inline ll solve(ll a,ll b,ll n) { ll sol,x,y; ll d=gcd(a,n,x,y); if (b%d==0) { sol=x*b/d; ll r=n/d; sol=(sol%r+r)%r; return sol; } else return -1; } inline bool merge(ll a1,ll n1,ll a2,ll n2,ll &a,ll &n) { ll x,y,c=a2-a1; ll d=gcd(n1,n2,x,y); ll K=solve(n1,c,n2); if (K==-1) return false; a=a1+n1*K; n=n1*n2/d; return true; } ll A,N; ll newa,newn; ll ans; int main() { int k; freopen("t.in","r",stdin); freopen("t.out","w",stdout); while (~scanf("%d",&k)) { int flag=0; scanf("%I64d%I64d",&N,&A); for (register int i=1;i


热门文章