c637: 滿滿的糖果屋 #3

2021-06-13 15:01:30 +0800 CST Tags: big-128, c.r.t

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

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

解法：這題和 c641 幾乎一模一樣，差別只在方程式數量跟所有質數的乘積超過 long long 兩件事而已。方程式數量不影響演算法運作，而質數乘積最大不超過 $10^{27}$，同時也不超過 128-bit 數據範圍 $(2^{127}-1\approx 10^{38.\sim})$，於是這題可以放心地使用 __int128_t 取代 long long。

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4inline __int128_t nnm(__int128_t i, __int128_t n) { // nonnegative modulo
 5    return (i % n + n) % n;
 6}
 7
 8string to_string(__int128_t x) {
 9    string result;
10    while (x > 0) {
11        result += x % 10 + '0';
12        x /= 10;
13    }
14    if (result.empty()) result += '0';
15    reverse(result.begin(), result.end());
16    return result;
17}
18
19int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
20    string line; __int128_t r[10], m[10]; int r2[10], m2[10];
21    while (getline(cin, line)) { istringstream iss; int n;
22        n=-1; iss.str(line); while (iss >> m2[++n]) m[n] = m2[n]; iss.clear();
23        getline(cin, line); n=-1; iss.str(line); while (iss >> r2[++n]) r[n] = r2[n];
24        int maxM = *max_element(m, m+n);
25        // let x = r[0] (mod m[0]) and x = r[1] (mod m[1]),
26        // then m[0] * t + r[0] = r[1] (mod m[1])
27        //  ==> m[0] * t + m[1] * k = r[1] - r[0] (mod m[1]).
28        // Suppose m[0] * t0 + m[1] * k0 = 1, then
29        // x == m[0] * t0 * {r[1] - r[0] (mod m[1])} + r[0] (mod m[0]*m[1]).
30        for (int i=0; i+1<n; i++) {
31            __int128_t a=m[i], b=m[i+1], x1=1, y1=0, x2=0, y2=1;
32            do {
33                __int128_t q = (a*x1 + b*y1) / (a*x2 + b*y2);
34                __int128_t x3 = x1 - q*x2;
35                __int128_t y3 = y1 - q*y2;
36                x1 = x2; y1 = y2; x2 = x3; y2 = y3;
37            } while (a*x2 + b*y2);
38            x1 = (x1 + b) % b; // x1 is t0 mentioned above.
39            r[i+1] = m[i] * x1 * nnm(r[i+1]-r[i], m[i+1]) + r[i];
40            m[i+1] *= m[i];
41            r[i+1] %= m[i+1];
42        }
43        cout << to_string(r[n-1] + (r[n-1]<=maxM) * m[n-1]) << '\n';
44    }
45    return 0;
46}

no image