poj 1006 Biorhythms 线性同余式 中国剩余定理（CRT）

缘起

中国剩余定理（CRT）是数论中非常著名的一个定理. 因为最早见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知其数”问题 ，所以又叫孙子定理. 用现代数学的话来说, CRT解决了一元一次同余方程组
$$
(S)：\begin{cases}
x≡a_1 (mod \ m_1) \
x≡a_2 (mod \ m_2) \
…\
x≡a_n (mod \ m_n) \
\end{cases}
$$
其中，m1,…,mn 这n个整数两两互质.

分析

CRT告诉我们对于任何整数a1,..,an, (S)有解，并且解可以如下构造出来

令 $M=m_1m_2…*m_n, M_i=M/m_i\ 1\le i\le n , \ t_i为M_i关于m_i）$的逆元（参见【1】） , 则

S 的通解如下
$$
x = kM+\Sigma_{1\le i \le n}a_it_iM_i
$$
k是整数. 所以求解CRT问题本质上可以归结于逆元的求解. 求逆元当然可以使用【1】中的办法，但是这里学习一种相比于逆元更加广泛的问题——求解线性同余式. 即此算法求解的是满足
$$
ax≡r\ (mod \ m)
$$
的x. 求法和【1】中涉及的思想是完全一样的（也是 ax+my=r, 然后得到通解, 然后根据需求是否求最小正整数解）.

于是我们使用CRT求解 poj 1006 Biorhythms 这道题

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
28
29
30
31
32
33
34
35
36
有些人认为一个人生命中有三个周期从他或她出生的那一天开始。这三个周期是身体，情绪和智力周期，它们的周期分
别为23,28和33天。每个周期中有一个峰值。在一个周期的高峰期，一个人在相应的领域（身体，情感或精神）中表现
最佳。例如，如果是精神曲线，思维过程将更加清晰，集中将更容易。
由于三个循环具有不同的周期，因此三个循环的峰值通常在不同的时间发生。我们想确定任何人何时出现三峰（所有三
个周期的峰值出现在同一天）。对于每个周期，您将获得从当前年度开始的一个峰值（不一定是第一个）发生的天数。
您还将获得一个日期，表示为从当年年初开始的天数。您的任务是确定从给定日期到下一个三峰的天数。给定日期不计
算在内。例如，如果给定日期为10且下一个三峰值出现在第12天，则答案为2，而不是3.如果在给定日期出现三峰值，
则应给出下一次出现的天数三峰。

【输入】
多样例。每种情况的输入由一行四个整数p，e，i和d组成。 值p，e和i分别是从当前年份开始的身体，
情绪和智力周期达到峰值的天数。 值d是给定日期，并且可以小于p，e或i中的任何一个。 所有值均为非负数且最多
为365，您可以假设在给定日期的21252=(23*28*33)天内将出现三峰值。 输入的结束由一行表示，其中p = e = 
i = d = -1。

【输出】
对每个样例，打印形如
Case 1: the next triple peak occurs in 1234 days.
注意，哪怕答案是1天之后, 也用days而不需要改成day

【样例输入】
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

【样例输出】
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.

显然，根据CRT，答案是 $(pt_1M_1+et_2M_2+it_3M_3)\%M-d$

其中M=m1m2m3, m1=23,m2=28,m3=33, M1=m2*m3, M2=m1*m3, M3=m1*m2, ti是Mi关于mi的逆元（参见【1】）

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int p,e,i,d;

int extgcd(int a, int b, int &x, int &y)
{
	if (!b)
	{
		x = 1,y=0;
		return a;
	}
	int ans = extgcd(b, a%b, x,y), t;
	t = x, x = y, y = t-a/b*y;
	return ans;
}

int inv(int a, int b) // 求a关于b的逆元, 即ax+by=1,a,b都是正整数
{
	int x,y;
	int gcd = extgcd(a,b,x,y); // gcd显然是1（CRT的假设是m1,..,mn两两互质）
	if (b>0)
	{
		while(x<0)x+=b;
		while(x>b)x-=b;
	}
	else
	{
		while(x<0)x-=b;
		while(x>-b)x+=b;
	} //求出的x就是a关于b的逆元
	return x;
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int cse = 0;
	while(~scanf("%d%d%d%d", &p, &e, &i,&d), ~p)
	{
		int M = 23*28*33, M1 = 28*33, M2 = 23*33, M3=23*28;
		int t1 = inv(M1, 23), t2 = inv(M2, 28), t3=inv(M3, 33);
		int ans = (p*t1*M1+e*t2*M2+i*t3*M3)%M;
		if(ans<=d)
		{
			ans+=M; // 特别的, ans=0, 则ans=M
		}
		printf("Case %d: the next triple peak occurs in %d days.\n",++cse, ans-d);
	}
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 84kB
Length 924
Lang C++
Submitted 2019-08-17 18:15:23
Shared
RemoteRunId 20758235

参考

【1】https://yfsyfs.github.io/2019/08/17/zoj-4712-Modular-Inverse-%E9%80%86%E5%85%83-%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97/