中國剩余定理說白了就是小學時候的韓信點兵的完全版。給定一系列數(shù)，給定條件是一個數(shù)MOD這一些列數(shù)的結(jié)果，問你最后這個數(shù)最少為多少。

抽象出來就是N個同余方程，利用擴展GCD就可以求得這一結(jié)果，本題給定的數(shù)都是互質(zhì)的，因此處理起來就簡單了。

代碼如下：

#include <cstdlib> #include <cstdio> #include <cstring> 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.\n", ++ca, ans - D);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Lyush/archive/2012/07/21/2602186.html

總結(jié)

以上是生活随笔為你收集整理的POJ-1006 Biorhythms 中国剩余定理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。