簡化後題目敘述

給你三個數字 $N_1, N_2, N_3$ 以及三個餘數 $x^3\bmod N_1, x^3\bmod N_2, x^3\bmod N_3$。已知對於所有 $i=1,2,3$ 皆有 $x^3 > N_i$、而且 $N_1, N_2, N_3$ 兩兩互質。求出滿足條件的最小 $x$。

輸入說明

輸入的第一列包含一個整數 $T$ ($1 \le $ $T$ $ \le 10$) 代表測試資料組數。對於每一組測試資料:第一列包含 $3$ 個整數 $N_{1}, N_{2}, N_{3}$ ($0 < $ $N_{1}, N_{2}, N_{3}$ $ < 2^{21}$)。第二列包含 $3$ 個整數 $x^3\bmod N_{1}, x^3\bmod N_{2}, x^3\bmod N_{3}$ 。

輸出說明

對於每筆測試資料輸出題目所求的 $x$ 值。

範例輸入

2
6 11 19
5 4 11
25 36 7
16 0 6

範例輸出

5
6

OJ 連結

題目出處:ICPC 2018 Asia Nakhon Pathom Regional


解法

對於輸入的三個 $x^3\bmod N_i$ 值來說,如果我們能分別找出所有可能的 $x\bmod N_i$ ($i=1,2,3$),那麼就可以利用中國剩餘定理,對所有可能的組合,計算出可能的 $x$。

參考程式碼

這題的測試資料看起來不太嚴謹。如果有發現可能有錯誤的地方再麻煩跟我說~謝謝!

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL inv(LL x, LL y, LL p = 1, LL q = 0, LL r = 0, LL s = 1) {
  return y ? p : inv(y, x % y, r, s, p - (x / y) * r, q - (x / y) * s);
}

// 使用條件:
// (1) 0 <= x1 < m1; 0 <= x2 < m2
// (2) m2 * m2 不會溢位。
// (3) 2 * m1 * m2 不會溢位。
LL CRT2(LL x1, LL m1, LL x2, LL m2) {
  LL t = inv(m1, m2);
  t %= m2;
  LL z = (t * (x2 - x1) % m2 + m2) % m2;
  return (x1 + z * m1) % (m1 * m2);
}

void solve() {
  int N[3], R[3] = {};
  for (int i = 0; i < 3; i++)
    cin >> N[i];
  for (int i = 0; i < 3; i++)
    cin >> R[i];
  vector<int> candidates[3];
  for (int i = 0; i < 3; i++)
    for (LL x = 0; x < N[i]; x++) {
      if (x * x * x % N[i] == R[i]) {
        candidates[i].push_back(x);
      }
    }
  vector<LL> sol;

  for (auto r1 : candidates[0])
    for (auto r2 : candidates[1])
      for (auto r3 : candidates[2]) {
        LL x = CRT2(r1, N[0], r2, N[1]);
        x = CRT2(x, (LL)N[0] * N[1], r3, N[2]);
        sol.push_back(x);
      }

  sort(sol.begin(), sol.end());
  int maxn = max(N[0], max(N[1], N[2]));
  for (auto s : sol)
    if (s * s > maxn || s * s * s > maxn) {
      cout << s << endl;
      break;
    }
}

int main() {
  int T;
  cin >> T;
  while (T--)
    solve();
  return 0;
}

關於競程日記

🍅 如果您想到更多有趣漂亮簡單乾淨的解法話歡迎留言給競程日記小編群!

ℹ️ 這是一篇投稿給競程日記的文章,歡迎大家投稿、交流與分享程式解題競賽的點點滴滴!

本文由卡恩(tmt514)撰寫。 本站使用 GasbyJS 搭配 Bulma 製作,其原始碼為 MIT 授權。 網站內容除了題源以外,若無特別說明皆為創用 CC-BY-NC-SA 4.0 授權。 題源部份若有版權爭議還請與我聯繫,感恩。