http://poj.org/problem?id=1006

中国剩余定理用来解求模方程组,用到了逆元。

这题三个数互质,直接用扩展欧几里德可得逆元。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; int a[],m[],n,d; void e_gcd(int a,int b,int &x,int &y)
{
if(!b)
{
x = ;
y = ;
return;
}
e_gcd(b,a%b,x,y);
int temp = x;
x = y;
y = temp-a/b*y;
} int CRT()
{
int M = ,ans = ;
for(int i = ;i <= n;i++) M *= m[i];
for(int i = ;i <= n;i++)
{
int x,y,Mi = M/m[i];
e_gcd(Mi,m[i],x,y);
ans = (ans+Mi*x*a[i])%M;
}
if(ans < ) ans += M;
return ans;
} int main()
{
n = ;
m[] = ;
m[] = ;
m[] = ;
int cnt = ;
while(scanf("%d%d%d%d",&a[],&a[],&a[],&d))
{
if(a[] == - && a[] == - && a[] == - && d == -) break;
int ans = CRT();
if(ans <= d) ans += ;
ans -= d;
printf("Case %d: the next triple peak occurs in %d days.\n",cnt++,ans);
}
return ;
}

最新文章

  1. 浅谈Js闭包现象
  2. java操作Redis
  3. 【转载】Android 自动化测试 Emmagee
  4. 微信支付系列(2)——jsapi支付源码解析
  5. js-特效部分学习-拖拽效果
  6. Mono for Android布局控件属性小结
  7. python3使用requests发闪存
  8. Android之布局
  9. Qt的皮肤设计(Style Sheet)
  10. 关于Android4.x系统默认显示方向各种修改
  11. 搭建Windows下Java Web开发环境
  12. Oracle表解锁
  13. csdn仍是&amp;quot;待定&amp;quot;对?
  14. js监听键盘方向键事件
  15. C#监控类属性的更改(大花猫动了哪些小玩具)
  16. django之快速分页
  17. TestNG 自动化测试入门教程--典型示例
  18. Cleartext HTTP traffic to xxx not permitted解决办法
  19. url两次编码
  20. Android studio新建文件出现setContentView(R.layout.activity_main);中的R标红错误解决方法

热门文章

  1. red note8 pro谷歌套件
  2. 不只是安装,Kolla 让 OpenStack 运维变简单
  3. .Net Core Web Api实践(四)填坑连接Redis时Timeout performing EVAL
  4. Linux 编程题
  5. Burpsuite设置拦截response
  6. Elastcisearch.Nest 7.x 系列`伪`官方翻译:通过 NEST 来快捷试用 Elasticsearch
  7. [bzoj4873] [洛谷P3749] [Shoi2017] 寿司餐厅
  8. 「 从0到1学习微服务SpringCloud 」04服务消费者Ribbon+RestTemplate
  9. umake ide -h
  10. 浅谈synchronized