中国余数定理与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]);
	}
}

附件: 

POJ-1006演算过程