SYCOJ798Biorhythms
2024-09-07 22:13:40
https://oj.shiyancang.cn/Problem/798.html
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 21252;
ll a[4],m[4];
ll M;
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
if(b==0){x=1,y=0;return a;}
ll d=ex_gcd(b,a%b,x,y);
ll temp=x;x=y;y=temp-a/b*y;
return d;
}
ll crt(ll n)
{
ll i,Mi,xi,yi,d,Ans=0;
M=1;
for(i=1;i<=n;i++)M*=m[i];
for(i=1;i<=n;i++)
{
Mi=M/m[i];d=ex_gcd(Mi,m[i],xi,yi);
Ans=(Ans+Mi*a[i]*xi)%M;
}
return (Ans%M+M)%M;//最小整数解,因为gcd为1所以直接M就可以了
}
int main()
{
ll k,t=0;
m[1]=23,m[2]=28,m[3]=33;
while(~scanf("%lld%lld%lld%lld",&a[1],&a[2],&a[3],&k),a[1]!=-1||a[2]!=-1||a[3]!=-1||k!=-1)
{
ll ans=crt(3);
while(ans<=k) ans+=M;//要超过k才行
printf("Case %lld: the next triple peak occurs in ",++t);
cout<<ans-k<<" days.\n";
}
return 0;
}
特殊情况的中国剩余定理,直接构造,因为gcd为1,并且在模M下具有唯一解,所以正常的模M就可以了。
但是要大于k,所以要到k之后。
最新文章
- 安装AdventureWorks2008R2
- Enumerators and Enumerable
- spark mllib 之线性回归
- js 闭包理解
- Html4与Html5的关键区别
- JS 回车提交
- PHP-Wamp集成包安装教程
- Expression构建DataTable to Entity 映射委托
- 普林斯顿大学算法课 Algorithm Part I Week 3 排序稳定性 Stability
- 第十七章——配置SQLServer(2)——32位和64位系统中的内存配置
- css3部分属性兼容性别扭写法(因为很多我就叫他别扭了,希望全面早早支持css3吧)
- SQL SERVER大话存储结构(4)_复合索引与包含索引
- db2中left()函数和right()函数对应oracle中的substr()函数
- Spring(二)IOC底层实现原理
- golang逃逸分析和竞争检测
- Android GridView 滑动条设置一直显示状态
- 涨知识,涨知识 :ThinkPHP框架下Where条件查询Mysql数据库某字段是否为空
- deque_01
- 20170716xlVba销售明细转销售单据
- GO1.6语言学习笔记1-基础篇