Biorhythms~~中国剩余定理

中国剩余定理,,百度一下,就有它的定义与证明。

这里我就讲一个例子就好了。

题目的意思就是给你p,e,i,d。(n + d)% 23 = p,(n + d) % 28 = e,(n + d) % 33 = i。求最小n。

将n+d看成一个整体,m =n + d。

要求m:

先使 28 * 33 * a % 23 = 1,求出a,x = 28 * 33 * a;

使 23 * 33 * b % 28 = 1,求出b,y = 23 * 33 * b;

使23 * 28 * c % 33 = 1,求出c,z = 23* 28 * c;

m = (p*x + e*y + i*z)% (23,28,33)的最小公倍数。

先求出x ,y,z。

<span style="white-space:pre"></span>int x, y, z;int a = 1;while((28 * 33 * a % 23) != 1){a++;}x = 28 * 33 * a;a = 1;while((23 * 33 * a % 28) != 1){a++;}y = 23 * 33 * a;a = 1;while((23 * 28 * a % 33) != 1){a++;}z = 23 * 28 * a;cout << x << ' ' << y << ' ' << z << endl;求出的x = 5544,y = 14421,z = 1288.

k = lcm(23, 28,33),k = 21252

下面的是AC的代码:

#include <iostream>using namespace std;int main(){int p, e, i, d, count = 1;int k = 21252;int x = 5544, y = 14421, z = 1288;while(cin >> p >> e >> i >> d){if(p == -1 && e == -1 && i == -1 && d == -1)break;int m = (p * x + y * e + z * i) % k;if(m – d == 0)m = 21252;else if(m – d < 0){m = m – d;m += 21252;}elsem -= d;cout << "Case " << count++ << ": the next triple peak occurs in " << m << " days." << endl;}return 0;}刚学到中国剩余定理,还要继续努力加油!!~~~

终究还是会从指缝中一滴一滴流淌干净。

Biorhythms~~中国剩余定理

相关文章:

你感兴趣的文章:

标签云: