中国余数定理与POJ 1006
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 这道《孙子算经》中的例题是小学或者初中数学竞赛里常见的同余问题。想当年自己解这类问题多是凑数凑出来的，而并不得其法。因此也经常焦头烂额。昨天看到 POJ 1006 ，突然又心血来潮想探寻一下这类问题是否有标准的解法。
浏览于Wikipedia之中，发现了几篇很好的文章：
Modular Arithmetic
Linear Congruence Theorem
Chinese Remainder Theorem
这里以“POJ 1006”:http://acm.pku.edu.cn/JudgeOnline/problem?id=1006 为例演示一下这个计算过程：
“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知”
推导过程见附件
#include <stdio.h>
int main()
{
int x, p, e, i ,d, k, n = 0, r[1024];
do {
scanf("%d%d%d%d", &p, &e, &i, &d);
if (p == -1 && e == -1 && i == -1 && d == -1) break;
p = p % 23;
e = e % 28;
i = i % 33;
/* x = 21252 * k - 504504 * p + 503217 * e + 1288 * i; */
x = (21252 + 5544 * p + 14421 * e + 1288 * i - d) % 21252;
r[n++] = (x == 0)?21252:x;
} while (1);
for (i = 0; i < n; i++) {
printf("Case %d: the next triple peak occurs in %d days.\n", i + 1, r[i]);
}
}
Attachment:
如果循环的次数超过1024，那么数组就越界了
恩，确实。应该弄一个越界判断。当时是因为通过测试了就没再管它了。