小小的模线性方程(组)

2019-04-13 17:25发布

站内文章 / 模拟电子
15830 0 967

1).poj1006.生理周期

已知四个数 p, e, i, d，求一个数 a，满足 a % 23 = p，a % 28 = e，a % 33 = i，输出 a - d。特别地，a 不能超过 21252。 因为 23，28，33 两两互质，所以这道题就是中国剩余定理。 #include using namespace std; typedef long long LL; LL p, e, i, lcm, d; int tot = 0; void doit() { ++ tot; lcm = 21252; LL t = (5544 * p + 14421 * e + 1288 * i - d + lcm) % lcm; if (t == 0) t = 21252; printf("Case %d: the next triple peak occurs in %lld days. ", tot, t); } int main() { while (scanf("%lld%lld%lld%lld", &p, &e, &i, &d) != EOF){ if (p == -1 && e == -1 && i == -1 && d == -1) break; doit(); } return 0; }

2).poj2891.Strange Way to Express Integers

x = ri (mod ai)，求x 的最小非负整数值。 中国剩余定理？不能用啦！因为没有保证 ai 互质。换一种方法？ 假设我们已经求出了前若干个方程的一个解 T，之前的方程中所有ai的最小公倍数为 lcm。可以发现 T+k*lcm（k 为常数）也是前若干个方程的解。加入当前方程后，问题转化为：找到一个 k，使 (T + k * lcm) mod ai = ri，也就是lcm * k ≡ ri - T (modai)。这又是一个一次线性同余方程的问题了。因此用 exgcd 解 N 次线性同余方程，就可以求出这个线性同余方程组的解。 #include using namespace std; typedef long long LL; int n; LL a1, a2, r1, r2, x, y, d; void init() { scanf("%I64d%I64d", &a1, &r1); } void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y) { if (!b){ x = 1; y = 0; d = a; return; } else { ex_gcd(b, a % b, d, x, y); int t = x; x = y; y = t - a / b * x; } } void doit() { bool flag = 1; for (int i = 2; i <= n; i ++){ scanf("%I64d%I64d", &a2, &r2); LL a = a1, b = a2, c = r2 - r1; ex_gcd(a, b, d, x, y); if (c % d) flag = 0; LL t = b / d; x = (((x * c / d) % t) + t) % t; r1 = a1 * x + r1; a1 = a1 * a2 / d; } if(!flag) r1 = -1; printf("%I64d ", r1); } int main() { while(scanf("%d", &n) != EOF){ init(); doit(); } return 0; }


热门文章