POJ-1006 Biorhythms 中国剩余定理

中国剩余定理说白了就是小学时候的韩信点兵的完全版。给定一系列数，给定条件是一个数MOD这一些列数的结果，问你最后这个数最少为多少。

抽象出来就是N个同余方程，利用扩展GCD就可以求得这一结果，本题给定的数都是互质的，因此处理起来就简单了。

代码如下：

#include 
#include 
#include 
using namespace std;int b[4], D;int ext_gcd(int a, int b, int &x, int &y)
{int ret, temp;if (b == 0) {x = 1, y = 0;return a;}ret = ext_gcd(b, a % b, x, y);temp = x, x = y, y = temp-a/b*y;return ret; 
}int main()
{int ca = 0, ans, x, y, MOD;while (scanf("%d %d %d %d", &b[1], &b[2], &b[3], &D) == 4) {if (b[1] == -1 && b[2] == -1 && b[3] == -1 && D == -1) {break;}ans = 0;MOD = 23*28*33;ext_gcd(28*33, 23, x, y);ans = (ans + b[1] * x * 28 * 33) % MOD;ext_gcd(23*33, 28, x, y);ans = (ans + b[2] * x * 23 * 33) % MOD;ext_gcd(23*28, 33, x, y);ans = (ans + b[3] * x * 23 * 28) % MOD;if (ans <= D) {ans += MOD;}printf("Case %d: the next triple peak occurs in %d days.
", ++ca, ans - D);}return 0;
}