POJ_1006_中国剩余
2024-09-06 18:44:07
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 ;
}
最新文章
- 浅谈Js闭包现象
- java操作Redis
- 【转载】Android 自动化测试 Emmagee
- 微信支付系列(2)——jsapi支付源码解析
- js-特效部分学习-拖拽效果
- Mono for Android布局控件属性小结
- python3使用requests发闪存
- Android之布局
- Qt的皮肤设计(Style Sheet)
- 关于Android4.x系统默认显示方向各种修改
- 搭建Windows下Java Web开发环境
- Oracle表解锁
- csdn仍是&;quot;待定&;quot;对?
- js监听键盘方向键事件
- C#监控类属性的更改(大花猫动了哪些小玩具)
- django之快速分页
- TestNG 自动化测试入门教程--典型示例
- Cleartext HTTP traffic to xxx not permitted解决办法
- url两次编码
- Android studio新建文件出现setContentView(R.layout.activity_main);中的R标红错误解决方法
热门文章
- red note8 pro谷歌套件
- 不只是安装,Kolla 让 OpenStack 运维变简单
- .Net Core Web Api实践(四)填坑连接Redis时Timeout performing EVAL
- Linux 编程题
- Burpsuite设置拦截response
- Elastcisearch.Nest 7.x 系列`伪`官方翻译:通过 NEST 来快捷试用 Elasticsearch
- [bzoj4873] [洛谷P3749] [Shoi2017] 寿司餐厅
- 「 从0到1学习微服务SpringCloud 」04服务消费者Ribbon+RestTemplate
- umake ide -h
- 浅谈synchronized