本题难度不大，为算法入门难度，但是是一道很经典的解同余方程组的问题。需要注意的是，本题暴力解法会超时，需要额外了解数论中的“孙子定理”才能设计出 AC 的程序。
一些人认为人体有各种不同的生物节律，即每过一段时间人体各个器官或系统的状态会发生周期性的改变。有一种理论认为，人体的体格、心理和智力节律各不相同，各自循环周期为 23、28、33 天。假设各个周期中总有状态“高峰”的一天，那么在不断循环中 3 个“高峰”总会有重叠的一天，即总状态的“最高峰”。
本题会给出 3 个循环的不同“高峰”时刻，以及上一次“最高峰”的时刻，求出下一次“最高峰”的时刻。
输入为 4 个非负整数，最大值为 365，前 3 个数为 3 中循环“高峰”的时刻，第 4 个数表示上一次“最高峰”的时刻。所有的时刻都是从 0 开始，用天数计数表第几天。最后，如果四个输入的数字都为 -1，则表示输入结束。
示例输入为：
1
2
3
4
5
6
7
| 0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
|
最后输出紧接着的“最高峰”的时刻与上一次“最高峰”的时刻之间相差的天数，其中上一个“最高峰”时刻不计数，即如果上一次“最高峰”为第 10 天，下一次为第 12 天，那么结果应输出 2。注意本题中的输出还有其他的格式要求。
对应示例输入的输出应为：
1
2
3
4
5
6
| Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
|
周期循环问题，一般都涉及余数问题，而多个周期同时进行则多要求求解一次同余方程组，常常会用到“大衍求一术”。
孙子定理源于《孙子算经》中的“物不知数”问题：“今有物不知其数，三三数之余二 ，五五数之余三 ，七七数之余二，问物几何？”
翻译为：一个数，被 3 除余数为 2，被 5 除余数为 3，被 7 除余数为 2，这个数是多少？
即一次同余方程组
1
2
3
| n % 3 = 2
n % 5 = 3
n % 7 = 2
|
原文中也给出了针对性的解法：“答曰：二十三。术曰：三三数之，賸二，置一百四十；五五数之，賸三，置六十三；七七数之，賸二 ，置三十。并之，得二百三十三，以二百一十减之，即得。凡三三数之，賸一，则置七十；五五数之，賸一，则置二十一；七七数之，賸一，则置十五。一百六以上，以一百五 减之，即得。”
即 n = (5 * 7 * 2) * 2 + (3 * 7 * 1) * 3 + (3 * 5 * 1) * 2 - (3 * 5 * 7) * 2 = 23
秦九韶在《数学九章》中对于孙子问题给出了通用的解法，可以解答任意正整数相关的一次同余方程组。当然，本题中的例子很简单，23、28、33 是互质的，是“大衍求一术”中的最简单问题。本题解法仍然类似上述《孙子算经》中的问题，关键是理解上述题目解法的原理，而后设计程序。
实际上，本题解题思路是“构造法”：
- 我们知道对于正整数
a % b = c 则有 a * d % b = (c * d) % b。 - 对于《孙子算经》问题的任意一个条件，比如：除以 3 余 2，可以构造一个数除以 3 余 1，而后令这个数乘以 2 就能满足余 2 的条件。
- 继续构造，令第 2 步中的数能够被 5 和 7 整除，而后对于 5 和 7 采用类似构造方法，分别构造出能被 3 和 7 整除且除以 5 余 1 的数，和能够被 3 和 5 整除且除以 7 余 1 的数
- 将第 3 步中构造的三个数，分别乘以对应的余数，然后三者相加，这样得到的数必定符合题目要求
- 对第 4 步得到的数再除以 3、5、7 的最小公倍数 105，求得到的余数，就是本题的最小正整数解
在“大衍求一术”中，对应各个构造的数有特定的称谓，利用算式解释为：
1
2
3
4
5
6
7
8
9
10
11
12
| 3、5、7 为“问数”，而当它们互质的时候也是“定母”。
要构造除以一个定母余数为 1 且整除其余定母的数，可以使用如下发生构造：
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；
这样得到的 a、b、c 被成为“乘率”。
对应 3、5、7 则有 5 * 7、3 * 7、3 * 5 和 a、b、c 相乘以保证可以整除其他定母，被成为“衍数”。
然后，同一个定母对应的衍数、乘率、余数相乘，再将 3 个乘积相加得到结果为 233。
最后，233 % 105 = 23
|
可以看出，其中最关键的是根据衍数求解乘率，一旦乘率得解则问题迎刃而解。
本题会给出四个输入分别记为 a、b、c、d，实际结果为先求解方程组：
1
2
3
| n % 23 = a
n % 28 = b
n % 33 = c
|
然后得出 n 的值，(n - d) % (23 * 28 * 33) 即可，最后注意如果结果不大于零，则根据余数性质再加上 23 * 28 * 33 = 21252 即可。
为了使得本题的程序尽量简单，可以尝试先在程序外求解一些与输入无关的计算数据，即把乘率笔算出来：
1
2
3
4
5
6
7
| 求乘率，以及乘率和衍数的乘积：
使 33 * 28 * x % 23 = 1，得乘率 x = 6；乘率乘衍数为 33 * 28 * 6 = 5544。
使 23 * 33 * y % 28 = 1，得乘率 y = 19；乘率乘衍数为 23 * 33 * 19 = 14421。
使 23 * 28 * z % 33 = 1，得乘率 z = 2；乘率乘衍数为 23 * 28 * 2 = 1288。
那么，最后可以得到：n = (5544 * a + 14421 * b + 1288 * c - d) % 21252
如果 n 不大于零，则 n = n + 21252
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import java.util.Scanner;
/**
*
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int d1 = 23;
int d2 = 28;
int d3 = 33;
int product = d1 * d2 * d3;
int count = 1;
while (in.hasNext()) {
int m1 = in.nextInt();
int m2 = in.nextInt();
int m3 = in.nextInt();
int start = in.nextInt();
if (m1 == -1 && m2 == -1 && m3 == -1 && start == -1) break;
int re = (5544 * m1 + 14421 * m2 + 1288 * m3 - start) % product;
if (re <= 0) re += product;
System.out.printf("Case %d: the next triple peak occurs in %d days.\n", count++, re);
}
}
}
|
本题中的代码经过笔算简化之后显得特别的简单，如果要完全安装“大衍求一术”的过程去写程序而非笔算也是可以的，但原理已经阐明过程就不再赘述。
维基百科之大衍求一术