中国剩余定理模板poj1006
2024-08-25 14:57:49
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm> using namespace std;
typedef long long ll;
const int maxn = ;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == )
{
x = ;
y = ;
return a;
}
ll r = exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - a / b * y;
return r;
}
ll china_remainder(int a[], int w[], int n)//w存放除数,a存放余数
{
ll M = , ans = , x, y;
for (int i = ; i < n; i++)
M *= w[i];
for (int i = ; i < n; i++)
{
ll m = M / w[i];
exgcd(m, w[i], x, y);
ans = (ans + x * m * a[i]) % M;
}
return (ans % M + M) % M;
}
int main()
{
int T, m, a[maxn], w[maxn];
w[] = ; w[] = ; w[] = ;
ll n = ;
int p, e, i, d, kase = ;
while (~scanf("%d %d %d %d", &p, &e, &i, &d))
{
if (p == - && e == - && i == - && d == -)
break;
a[] = p;
a[] = e;
a[] = i;
ll ans = china_remainder(a, w, n);
ans -= d;
int mod = w[] * w[] * w[];
ans = (ans % mod + mod) % mod;
if (ans == )
ans = mod;
printf("Case %d: the next triple peak occurs in %lld days.\n", ++kase, ans); }
return ;
}
最新文章
- Android自定义折线图
- 如何安装node.js支持插件
- java 多线程4(死锁)
- 微软Azure已开始支持hadoop--大数据云计算
- .Net Service部署(二)
- J2SE知识点摘记(七)
- 给负载均衡器添加多IP
- java中this的N种使用方法
- Servlet以及单例设计模式
- 字符输出流 FileWriter
- STL详解
- python--model进阶
- Unity5权威讲解+项目源码+MP4
- acdream 20140730 D题
- 【bzoj2669】 cqoi2012—局部极小值
- jstl $前 出现 空格 ,可能出现无法解析的 情况
- ES6学习笔记(一)-变量的解构赋值
- 006-动态生成验证码Servlet代码模板
- win10下ndk编译arm可执行体
- (1)、hive框架搭建和架构简介