c641: 滿滿的糖果屋 #2

2021-06-12 23:11:52 +0800 CST Tags: c.r.t

出處：https://zerojudge.tw/ShowProblem?problemid=c641
提交：https://zerojudge.tw/Submissions?problemid=c641&account=allllllan123456

問題：給你三組 $x\equiv r_i$ (mod $p_i$)，其中 $p_i$ 為相異質數，且 $0\lt r_i\lt p_i\lt 100$，請找出滿足方程組並且大於所有 $p_i$ 的最小正整數 $x_0$。

解法：此乃中國剩餘定理的經典題型，本筆記有專頁解說。惟這題有特別要求 $x_0$ 要大於所有的 $p_i$，第 29 行的答案要特別檢查。

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4inline int nnm(int i, int n) { // nonnegative modulo
 5    return (i % n + n) % n;
 6}
 7
 8int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 9    int r[3], m[3];
10    while (cin >> m[0] >> m[1] >> m[2] >> r[0] >> r[1] >> r[2]) {
11        int maxM = *max_element(m, m+3);
12        // let x = r[0] (mod m[0]) and x = r[1] (mod m[1]),
13        // then m[0] * t + r[0] = r[1] (mod m[1])
14        //  ==> m[0] * t + m[1] * k = r[1] - r[0] (mod m[1]).
15        // Suppose m[0] * t0 + m[1] * k0 = 1, then
16        // x == m[0] * t0 * {r[1] - r[0] (mod m[1])} + r[0] (mod m[0]*m[1]).
17        for (int i=0; i+1<3; i++) {
18            int a=m[i], b=m[i+1], x1=1, y1=0, x2=0, y2=1;
19            do {
20                int q = (a*x1 + b*y1) / (a*x2 + b*y2);
21                int x3 = x1 - q*x2;
22                int y3 = y1 - q*y2;
23                x1 = x2; y1 = y2; x2 = x3; y2 = y3;
24            } while (a*x2 + b*y2);
25            x1 = (x1 + b) % b; // x1 is t0 mentioned above.
26            r[i+1] = m[i] * x1 * nnm(r[i+1]-r[i], m[i+1]) + r[i];
27            m[i+1] *= m[i];
28            r[i+1] %= m[i+1];
29        }
30        cout << r[2] + (r[2]<=maxM) * m[2] << '\n';
31    }
32    return 0;
33}

no image