poj 1006 題的思路不是很難的，可以轉化數學式：
現設 num 是下一個相同日子距離開始的天數
p，e，i，d 如題中所設！
那麼就可以得到三個式子：( num + d ) % 23 == p； ( num + d ) % 28 == e； ( num + d ) % 33 == i；
p，e，i，d 是我們輸入的，那麼我們需要求出num即可，為了方便，我們將num+d暫時作為一個整體！令x = num + d；
即：x % 23 == p； x % 28 == e； x % 33 == i；求x
怎麼辦？這就涉及到所謂的 “ 中國剩余定理 ”( 概念自己google，很easy )
《孫子算經》中有“物不知數”問題：“今有物不知其數，三三數之余二 ，五五數之余三 ，七七數之余二，問物幾何？”答為“23”。
--------這個就是傳說中的“中國剩余定理”。 其實題目的意思就是，n % 3 = 2, n % 5 = 3, n % 7 = 2; 問n是多少？
那麼他是怎麼解決的呢？
看下面：
題目中涉及 3， 5，7三個互質的數、
令：5 * 7 * a % 3 = 1; --------------> a = 2; 即5 * 7 * 2 = 70；
3 * 7 * b % 5 = 1; --------------> b = 1; 即3 * 7 * 1 = 21；
3 * 5 * c % 7 = 1; --------------> c = 1; 即3 * 5 * 1 = 15；
為什麼要使余數為1：是為了要求余數2的話，只要乘以2就可以，要求余數為3的話，只要乘以3就可以！
( 因為題目想要n % 3 =2, n % 5 = 3, n % 7 =2; )
那麼：要使得n % 3 = 2，那麼（ 5 * 7 * 2 ）*2 % 3 = 2；( 因為5 * 7 * 2 % 3 = 1 )
同理： 要使得n % 5 = 3，那麼（ 3 * 7 * 1 ）*3 % 5 = 3；( 因為3 * 7 * 1 % 5 = 1 )
同理：要使得n % 7 = 2，那麼（ 3 * 5 * 1 ）* 2 % 7 = 2；( 因為3 * 5 * 1 % 7 = 1 )
那麼現在將（ 5 * 7 * 2 ）* 2和（ 3 * 7 * 1 ）* 3和（ 3 * 5 * 1 ）* 2相加會怎麼樣呢？我們知道
（ 5 * 7 * 2 ）* 2可以被5和7整除，但是%3等於2
（ 3 * 7 * 1 ）* 3可以被3和7整除，但是%5等於3
（ 3 * 5 * 1 ）* 2可以被3和5整除，但是%7等於2
那麼即使相加後，%3， 5， 7的情況也還是一樣的！
那麼就得到一個我們暫時需要的數（ 5 * 7 * 2 ）* 2 +（ 3 * 7 * 1 ）* 3 +（ 3 * 5 * 1 ）* 2 = 233
但不是最小的!所有我們還要 233 % ( 3 * 5 * 7 ) == 23 得解！
/******************************************************************************************************************************************************/
// 以上就是算法解析，貌似講的不是很清晰，哎，大家見諒咯~
現在看看此題：x % 23 == p； x % 28 == e； x % 33 == i；求x
按照以上算法：
使 33 * 28 * a % 23 = 1，得a = 6； 33 * 28 * 6 = 5544；
使23 * 33 * b % 28 = 1， 得b = 19；23 * 33 * 19 = 14421；
使23 * 28 * c % 33 = 1， 得c = 2； 23 * 28 * 2 = 1288。
那麼x = 5544 * p + 14421 * e + 1288 * i
那麼x-d即相差的時間天數！
因為有范圍限制，那麼(x-d) %= 21252；且如果此時<=0，那麼(x-d) += 21252 ，以上都只是為了保證在范圍內而已~
AC代碼如下：
[cpp] view plaincopyprint?
/*
中國剩余定理:出自《孫子算經》
*/
#include<stdio.h>
#define MAX 21252
int main()
{
int p, e, i, d, n, count = 0;
while( scanf("%d%d%d%d", &p, &e, &i, &d) != EOF )
{
count++;
if(p == -1 && e == -1 && i == -1 && d == -1)
{
break;
}
n = ( 5544 * p + 14421 * e + 1288 * i - d ) % MAX;
if( n <= 0 ) // 范圍限制
{
n += 21252;
}
printf("Case %d: the next triple peak occurs in %d days.\n", count, n );
}
return 0;
}
/*
中國剩余定理:出自《孫子算經》
*/
#include<stdio.h>
#define MAX 21252
int main()
{
int p, e, i, d, n, count = 0;
while( scanf("%d%d%d%d", &p, &e, &i, &d) != EOF )
{
count++;
if(p == -1 && e == -1 && i == -1 && d == -1)
{
break;
}
n = ( 5544 * p + 14421 * e + 1288 * i - d ) % MAX;
if( n <= 0 ) // 范圍限制
{
n += 21252;
}
printf("Case %d: the next triple peak occurs in %d days.\n", count, n );
}
return 0;
}
