第一种做法(暴力)
思路:
暴力求解,从j = p开始枚举到21252,因为21252是最大得数,将23 * 28 * 33 = 21252,所以最大的情况就是所有的都可以整除他们对应的除数,这样答案就是21252了,然后枚举的数如果符合样例,那么这个数就是答案,但是需要注意的是,答案要是正整数,如果是负数的话要转换成正数。
#include #include using namespace std; const int maxn = 21252; int main() { int p, e, i, d, Case = 0; while (scanf("%d %d %d %d", &p, &e, &i, &d) != EOF && p != -1) { p %= 23; e %= 28; i %= 33; int x; if (p == 0) p = 23; for (int j = p; j <= maxn; j += 23) { if (j % 28 == e && j % 33 == i) { x = j; break; } } if (x < d) x += maxn - d; else x -= d; printf("Case %d: the next triple peak occurs in %d days.\n", ++Case, x); } return 0; }
第二种做法(中国剩余定理)
思路:
x % m[0] = a[0];
x % m[1] = a[1];
x % m[2] = a[2];
题目让我们求x的值,符合这种式子的话有中国剩余定理,而剩余定理中分了互质与不互质两种情况,而28,33,23是互质的,这题的话实际上就是一个模板题,只要懂这个定理就可以套模板了。这里有一些关于中国剩余定理的知识中国剩余定理
#include #include using namespace std; typedef long long ll; const int lcm = 23 * 28 * 33; void Exgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return ; } Exgcd(b, a % b, x, y); int tmp = x; x = y; y = tmp - a / b * y; } int main() { ll m[5] = {23, 28, 33}, a[5]; ll p, e, i, d, Case = 0; while (scanf("%lld %lld %lld %lld", &a[0], &a[1], &a[2], &d) != EOF && a[0] != -1) { ll res = 0, x, y; for (int i = 0; i < 3; i++) { ll tmp = lcm / m[i]; Exgcd(tmp, m[i], x, y); x = (x % m[i] + m[i]) % m[i]; res = (res + x * a[i] * tmp) % lcm; } res = (res + lcm) % lcm; if (res <= d) res += lcm; printf("Case %lld: the next triple peak occurs in %lld days.\n", ++Case, res - d); } return 0; }