首页 > 代码库 > POJ 1006 Biorhythms 中国剩余定理
POJ 1006 Biorhythms 中国剩余定理
题目来源:POJ 1006 Biorhythms
题意:给出3个周期第一次发生的时间 和 当前开始的天数 求三个周期下一次到达高峰期发生在哪一天
思路:这题很水 试一下我的模版而已
#include <cstdio> #include <cstring> using namespace std; typedef long long LL; const int maxn = 10; int a[maxn], m[maxn]; //求整数x和y,使得ax+by=d, 且|x|+|y|最小。其中d=gcd(a,b) void gcd(LL a, LL b, LL& d, LL& x, LL& y) { if(!b) { d = a; x = 1; y = 0; } else { gcd(b, a%b, d, y, x); y -= x * (a/b); } } LL china(int n, int* a, int* m) { LL M = 1, d, y, x = 0; for(int i = 0; i < n; i++) M *= m[i]; for(int i = 0; i < n; i++) { LL w = M /m[i]; gcd(m[i], w, d, d, y); x = (x + y*w*a[i]) % M; } return (x+M)%M; } int main() { m[0] = 23; m[1] = 28; m[2] = 33; int cas = 1; int n; while(scanf("%d %d %d %d", &a[0], &a[1], &a[2], &n) != EOF) { if(a[0] == -1 && a[1] == -1 && a[2] == -1 && n == -1) break; int ans = china(3, a, m)-n; if(ans <= 0) ans += 21252; if(ans > 21252) ans %= 21252; printf("Case %d: the next triple peak occurs in %d days.\n", cas++, ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。