poj 1006 Biorhythms (中国剩余定理模板)
2024-08-26 19:57:59
http://poj.org/problem?id=1006
题目大意:
人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面表现出色。例如,智力周期的高峰,人会思维敏捷,精力容易高度集中。因为三个周期的周长不同,所以通常三个周期的高峰不会落在同一天。对于每个人,我们想知道何时三个高峰落在同一天。对于每个周期,我们会给出从当前年份的第一天开始,到出现高峰的天数(不一定是第一次高峰出现的时间)。你的任务是给定一个从当年第一天开始数的天数,输出从给定时间开始(不包括给定时间)下一次三个高峰落在同一天的时间(距给定时间的天数)。例如:给定时间为10,下次出现三个高峰同天的时间是12,则输出2(注意这里不是3)。
注意: 所求的时间小于21252。
根据题意可以得出公式:
(x + d)% 23 = p;
(x + d)% 28 = i;
(x + d)% 33 = e;
那么我们可以根据中国剩余定理求出x+d,就可以解题了
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<stdlib.h> using namespace std; typedef long long LL; void gcd(int a, int b, int &x, int &y)
{
if(b == )
{
x = ;
y = ;
return ;
}
gcd(b, a % b, x, y);
int k = x;
x = y;
y = k - a / b * y;
} int CRT(int a[], int b[], int n)
{
int M = , N, ans = , x, y;
for(int i = ; i < n ; i++)
M *= a[i];
for(int i = ; i < n ; i++)
{
N = M / a[i];
gcd(N, a[i], x, y);
ans += N * x * b[i];
}
return ans % M;
} int main()
{
int f = , d;
int a[] = {, , }, b[];
while()
{
f++;
for(int i = ; i < ; i++)
scanf("%d", &b[i]);
scanf("%d", &d);
if(d == -)
break;
int m = (CRT(a, b, ) - d) % ;
if(m <= )
m += ;
printf("Case %d: the next triple peak occurs in %d days.\n", f, m); }
return ;
}
最新文章
- C#:调用webservice时提示对操作的回复消息正文进行反序列化时出错
- Azure Automation (3) 定期将某个Azure订阅下的所有虚拟机开关机
- Android退出时关闭所有Activity的方法
- strace命令(收集整理,常看常新)
- Linux查看文件编码格式及文件编码转换
- python使用zlib实现压缩与解压字符串
- 头文件定义和ARM指令
- 将HTMLCollection/NodeList/伪数组转换成数组
- [原]捉虫记3:_ConectionPtr指针调用open失败
- c++11 auto_ptr介绍
- ckeditor_4.5.10_full上传图片功能
- 如何调试webservice接口是否正常
- HTTP中的Range: bytes=0-
- 18.25 JLink调试程序步骤
- 『TensorFlow』批处理类
- 《Mysql 引擎》
- Python记录2:数据类型
- Digital Deletions HDU - 1404
- PHP安全之webshell和后门检测(转)
- CentOs7 安装最新版的Git