poj1006 Biorhythms<中国剩余定理>

本题的主要知识点为：中国剩余定理

中国剩余定理是指若有一些两两互素的整数 $m_1, m_2, \ldots, m_n$ ，则对任意的整数： $a_1, a_2,...a_n$ ，以下联立同余方程组对模 $m_1 m_2 \cdots m_n$ 有公解，即：

$\left\{ \begin{matrix} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv a_n \pmod {m_n} \end{matrix} \right.$

经典例题就是韩信点兵了，韩信带2300左右名兵士打仗，战死四五百人，站3人一排，多出2人；站5人一排，多出3人；站7人一排，多出6人。韩信马上说出人数。

把问题简化为：已知 n%3=2, n%5=3, n%7=2, 求n。

因为n%3=2, n%5=3, n%7=2 且 3，5，7互质（互质可以直接得到这三个数的最小公倍数）

令x= n%3=2 ， y= n%5=3 ，z= n%7=2

　　　　使5×7×a被3除余1，有35×2=70，即a=2；

　　　　使3×7×b被5除余1，用21×1=21，即b=1；

使3×5×c被7除余1，用15×1=15，即c=1。

那么n =（70×x+21×y+15×z）%lcm(3,5,7) = 23 这是n的最小解

而韩信已知士兵人数在2300~2400之间，所以只需要n+i×lcm(3,5,7)就得到了2333，此时i=22。

形式化解释：

假设x是那个未知数，而除3，5，7后的余数分别为r1，r2，r3。因此有

x≡r1(mod 3)

x≡r2(mod 5)

x≡r3(mod 7)

（定理：如果 a%b=c，那么 (a*k)%b=kc (k为大于零的整数)）

第一步：就是找除了r[i]之外的所有余数r[j](j≠i)的乘积（最小公倍数）；

第二步：在求n1，n2，n3时又用了一个小技巧，以n1为例，并非从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。

第三步：n1+n2+n3只是问题的一个解，并不是最小的解，故最小解应是该解的等价类。

注：中国剩余定理的思想在于先找到一个满足条件的数，不管是不是最小的，如果不是最小的就不断减公倍数，中国剩余定理的巧妙在于把满足条件的数分成三个部分相加。

View Code

 1 #include <stdio.h>
 2 // 23 28 33
 3 int main( ) 
 4 {
 5     int p, e, i, d,t=1;
 6     while( scanf( "%d%d%d%d", &p, &e, &i, &d )==4 )
 7     {
 8         if( p==-1 && e==-1 && i==-1 && d==-1 )break;
 9         int lcm=21252;  // lcm(23,28,33)
10         int n=(p*5544+e*14421+1288*i-d+lcm)%lcm;// (28*33)*a%23==1 (23*33*b)%28==1  (23*28*c)%33==1
11         if( n==0 )n=lcm;
12         printf( "Case %d: the next triple peak occurs in %d days.\n", t++, n );
13     }
14     return 0;
15 }