結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー Tifa
提出日時 2023-09-12 02:00:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,585 bytes
コンパイル時間 832 ms
コンパイル使用メモリ 80,520 KB
最終ジャッジ日時 2025-02-16 21:44:16
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "test\\yukicoder\\448.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/448"

#line 1 "lib\\math\\crt.hpp"



#line 1 "lib\\util.hpp"



#include <cassert>
#include <cstddef>
#include <cstdint>
#include <type_traits>

namespace tifa_libs {

using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

}  // namespace tifa_libs


#line 5 "lib\\math\\crt.hpp"

#line 1 "lib\\math\\inv_gcd.hpp"



#line 5 "lib\\math\\inv_gcd.hpp"

#line 1 "lib\\math\\exgcd.hpp"



#line 5 "lib\\math\\exgcd.hpp"

#include <tuple>

namespace tifa_libs::math {

// @return tuple(g, x, y) s.t. g = gcd(a, b), xa + yb = g, |x| + |y| is the minimal (primary) and x <= y (secondarily)
constexpr std::tuple<u64, i64, i64> exgcd(i64 a, i64 b) {
  i64 x1 = 1, x2 = 0, x3 = 0, x4 = 1;
  while (b) {
    i64 c = a / b;
    std::tie(x1, x2, x3, x4, a, b) = std::make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b * c);
  }
  return {a, x1, x2};
}

}  // namespace tifa_libs::math


#line 7 "lib\\math\\inv_gcd.hpp"

namespace tifa_libs::math {

constexpr std::pair<u64, u64> inv_gcd(u64 n, u64 mod) {
  auto [g, x, y] = exgcd((i64)(n % mod), (i64)mod);
  return {g, x > 0 ? (u64)x : (u64)(x % (i64)mod + (i64)mod) % mod};
}

}  // namespace tifa_libs::math


#line 7 "lib\\math\\crt.hpp"

#include <vector>

namespace tifa_libs::math {

// solve x == r_i (mod m_i)
// @param lcm(m) < INT64_MAX
// @return {x, lcm(m)}
inline std::pair<u64, u64> crt(const std::vector<u64> &r, const std::vector<u64> &m) {
  assert(r.size() == m.size());
  size_t n = r.size();
  u64 r0 = 0, m0 = 1;
  for (size_t i = 0; i < n; i++) {
    assert(m[i]);
    u64 r1 = r[i] % m[i], m1 = m[i];
    if (m0 < m1) {
      std::swap(r0, r1);
      std::swap(m0, m1);
    }
    if (m0 % m1 == 0) {
      if (r0 % m1 != r1) return {0, 0};
      continue;
    }
    auto [g, im] = inv_gcd(m0, m1);
    u64 u1 = (m1 / g);
    if ((r1 - r0) % g) return {0, 0};
    u64 x = (r1 - r0) / g % u1 * im % u1;
    r0 += x * m0;
    m0 *= u1;
  }
  return {r0, m0};
}

}  // namespace tifa_libs::math


#line 4 "test\\yukicoder\\448.test.cpp"

#include <iostream>
#line 7 "test\\yukicoder\\448.test.cpp"

int main() {
  tifa_libs::i64 n;
  std::cin >> n;
  std::vector<tifa_libs::u64> r, m;
  r.reserve((size_t)n);
  m.reserve((size_t)n);
  while (n--) {
    tifa_libs::u64 x, y;
    std::cin >> x >> y;
    r.push_back(x);
    m.push_back(y);
  }
  auto [R, M] = tifa_libs::math::crt(r, m);
  std::cout << (M ? (tifa_libs::i64)R : -1) << '\n';
  return 0;
}
0