生理周期

中国剩余定理模板题

 1 #include<stdio.h>
 2 #include<string.h>
 3 int p,e,i,d;
 4 int a[5],m[5];
 5 int item = 1;
 6 int extend_gcd(int a,int b,int &x,int &y)
 7 {
 8     if(b == 0)
 9     {
10         x = 1;
11         y = 0;
12         return a;
13     }
14     else
15     {
16         int r = extend_gcd(b,a%b,x,y);
17         int t = x;
18         x = y;
19         y = t-a/b*y;
20         return r;
21     }
22 }
23 
24 void CRT()
25 {
26     int M = 1,tm,ret = 0;
27     for(int i = 0; i < 3; i++)
28         M*=m[i];
29     for(int i = 0; i < 3; i++)
30     {
31         int x,y;
32         tm = M/m[i];
33         extend_gcd(tm,m[i],x,y);
34         ret = (ret + tm*x*a[i])%M;
35     }
36     if(ret - d <= 0)
37         printf("Case %d: the next triple peak occurs in %d days.
",item,ret+M-d);
38     else printf("Case %d: the next triple peak occurs in %d days.
",item,(ret+M)%M-d);
39 }
40 
41 int main()
42 {
43 
44     while(~scanf("%d %d %d %d",&p,&e,&i,&d))
45     {
46         if(p == -1 && e == -1 && i == -1 && d == -1)
47             break;
48         a[0] = p;
49         a[1] = e;
50         a[2] = i;
51         m[0] = 23;
52         m[1] = 28;
53         m[2] = 33;
54         CRT();
55         item++;
56 
57     }
58     return 0;
59 }

View Code

中国剩余定理

设m1,m2,...,mk两两互质,则下面的同余方程组：
  x = a1 (mod m1)
  x = ak (mod mk)
  .
.
.
  x = ak (mod mk)

在0<=x<M = m1*m2*...*mk内有唯一解。
记Mi = M / mi (1<=i<=k) ,因为(Mi,mi)=1,故有两整数pi，qi满足Mi*pi + mi*qi = 1，
如果记ei = Mi*pi ，那么有
ei = 0 (mod mj) , j<>i
= 1 (mod mj) , j==i

很显然，e1*a1 + e2*a2 + ... + ek*ak 就时方程组的一个解 ，
这个解%M后就得到了最小的非负整数解；

求ei可以用扩展欧几里得来求；