POJ 1006 中国剩余定理

 1 #include <cstdio>
 2 int main()
 3 {
 4 //    freopen("in.txt","r",stdin);
 5     int p,e,i,d,kase=0;
 6     while(scanf("%d%d%d%d",&p,&e,&i,&d))
 7     {
 8         if(p==-1 && e == -1 && i == -1 && d== -1) break;
 9         const int m1 = 23,m2 = 28,m3 = 33;
10         const int M1 = m2*m3, M2 = m1*m3, M3 = m1*m2;
11         const  int m11 = 6,m22=19,m33=2;
12         const int M =m1*m2*m3;
13         int x = p*m11*M1 + e * m22*M2 + i * m33*M3;
14         x = (x+M)%M;
15         if(x-d <= 0 )
16             printf("Case %d: the next triple peak occurs in %d days.
",++kase,x-d+M);
17         else printf("Case %d: the next triple peak occurs in %d days.
",++kase,x-d);
18     }
19     return 0;
20 }

View Code

首先了解中国剩余定理，根据扩展欧几里得定理求出M1‘，M2'和M3’的正整数解分别为6,19,2。。。直接算的话M2‘为-9，但是要是正整数解，所以可以用-9+28 = 19.

下面介绍一下中国剩余定理，又叫孙子定理。

若m1,m2,```,mk为两两互质的k个整数，有数x%mi = bi(1<=i<=k).bi已知，求x的解

令M = m1*m2*```*mk,Mi = M/mi```Mi'为满足(Mi'Mi)%mi = 1的正整数解···

x = sum(bi*Mi' * Mi)%M````

验证x是解，用x%mi = bi```，然后证明x是唯一解，假设y也是解，得到x = y%M...所以x就是全部的解了·····

不明白还可以去看下面的链接：

http://www.cnblogs.com/walker01/archive/2010/01/23/1654880.html