题目
题目链接
大意是人体里有 3 个循环,分别为 23 天、28 天、33 天,一年有 21252 天,人体一年有一个高峰,即 3 个循环交汇的时候。这一天模 23, 28, 33 的结果分别为 , 今天是
天,问下一次高峰还要多少天才来。
思路
题目给出的条件相当于给出了 3 个同余方程,由于 23 28 33 这 3 个数互质,所以可以直接用中国剩余定理求解,求解出是第 天,结果就是
天,注意处理 0 和负数。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; int exgcd(int a, int b, int & x, int & y) { if (b == 0) { x = 1; y = 0; return a; } int tmp = exgcd(b, a % b, x, y); int x1 = y; int y1 = x - (a / b) * y; x = x1; y = y1; return tmp; } int a[4]; int m[4]; int ans, i, d; int CRT() { int ans = 0; int M = 21252; for (i = 1; i <= 3; ++i) { int Mi = M / m[i]; int t, y; exgcd(Mi, m[i], t, y); ans = (ans + a[i] * Mi * t) % 21252; } return ans; } int main() { m[1] = 23, m[2] = 28, m[3] = 33; int T = 0; while (~scanf("%d%d%d%d", &a[1], &a[2], &a[3], &d), !(a[1] == -1&&a[2] == -1&&a[3] == -1 && d == -1)) { ans = CRT(); ans = (ans - d) % 21252; if (ans <= 0) ans += 21252; printf("Case %d: the next triple peak occurs in %d days.\n", ++T, ans); } return 0; } |