洛谷题解 UVA756 【Biorhythms】

发表于 | 更新于 | 阅读次数：
本文字数： 1.5k | 阅读时长 ≈ 1 分钟

题目大意

一个人体力、情感、智力出现峰值的周期分别为23、28、33天，现在给出三者上一次出现峰值的日期$p,e,i$和现在的日期$d$，问经过几天三个峰值会出现在同一天。

思路

首先这一看就是中国剩余定理的模板题，

如果不知道中国剩余定理建议先学习再做本题，这样就会发现这题是非常简单的。

由题意和中国剩余定理可得以下方程组：

$$ \begin{cases} x≡p(mod\ 23) \ (1) \\ x≡e(mod\ 28) \ (2)\\ x≡i(mod\ 33) \ (3)\end{cases} $$

其中，该方程组可以化为以下形式：

$$(1) \begin{cases} x_1≡1(mod\ 23) \\ x_1≡0(mod\ 28) \\ x_1≡0(mod\ 33) \end{cases} $$

$$(2) \begin{cases} x_2≡0(mod\ 23) \\ x_2≡1(mod\ 28) \\ x_2≡0(mod\ 33) \end{cases} $$

$$(3) \begin{cases} x_3≡0(mod\ 23) \\ x_3≡0(mod\ 28) \\ x_3≡1(mod\ 33) \end{cases} $$

解以上方程组，有：

$$ \begin{cases} x_1=5544 \\ x_2=14421 \\ x_3=1288 \end{cases} $$

由中国剩余定理有：

$ lcm(23,28,33)=21252 $

$ ans+d≡p * x_1+e * x_2+i * x_3(mod \ 21252) $

化简得：

$ ans=(p * x_1+e * x_2+i * x_3-d+21252)\ mod\ 21252 $

即：

$ ans=(p * 5544+e * 14421+i * 1288-d+21252)\ mod\ 21252 $

这样我们就得到了本题的通解。

但是有个特殊情况，当$ans=0$时要输出$21252$，因为你要求的是下一次三者同一天。

Q：为什么通解中要$+21252$

A：因为题目中不能保证$d$一定小于$p$、$e$、$i$，所以为了避免$ans$变成负数，所以要先$+21252$再取模

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=21252;//lcm(23,28,33)
int p,e,i,d,cot;

int main()
{
	scanf("%d%d%d%d",&p,&e,&i,&d);
	while(p+e+i+d!=-4)
	{
		cot++;
		int ans=(5544*p+14421*e+1288*i-d+maxn)%maxn;//通解
		if(ans==0)//特判
		{
			ans=maxn;
		}
		printf("Case %d: the next triple peak occurs in %d days.\n",cot,ans);
		scanf("%d%d%d%d",&p,&e,&i,&d);
	}
	return 0;
}

题目详见:https://www.luogu.com.cn/problem/UVA756