結果

問題 No.187 中華風 (Hard)
ユーザー hly1204hly1204
提出日時 2022-05-15 01:36:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 77 ms / 3,000 ms
コード長 5,163 bytes
コンパイル時間 1,083 ms
コンパイル使用メモリ 93,116 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-23 13:06:13
合計ジャッジ時間 2,934 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 63 ms
6,940 KB
testcase_03 AC 62 ms
6,944 KB
testcase_04 AC 77 ms
6,940 KB
testcase_05 AC 76 ms
6,944 KB
testcase_06 AC 76 ms
6,940 KB
testcase_07 AC 76 ms
6,940 KB
testcase_08 AC 55 ms
6,940 KB
testcase_09 AC 55 ms
6,944 KB
testcase_10 AC 56 ms
6,940 KB
testcase_11 AC 76 ms
6,944 KB
testcase_12 AC 76 ms
6,944 KB
testcase_13 AC 14 ms
6,940 KB
testcase_14 AC 15 ms
6,944 KB
testcase_15 AC 62 ms
6,940 KB
testcase_16 AC 63 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 58 ms
6,944 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 76 ms
6,940 KB
testcase_23 AC 1 ms
6,944 KB
testcase_24 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#line 1 "math\\cra.hpp"



#line 1 "common.hpp"



#define LIB_DEBUG

#define LIB_BEGIN namespace lib {
#define LIB_END }
#define LIB ::lib::


#line 1 "math\\extended_gcd.hpp"



#line 5 "math\\extended_gcd.hpp"

#include <tuple>
#include <utility>
#include <vector>

LIB_BEGIN

// Input:  integer `a` and `b`.
// Output: (x, y, z) such that `a`x + `b`y = z = gcd(`a`, `b`).
[[deprecated]] std::tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
  long long x11 = 1, x12 = 0, x21 = 0, x22 = 1;
  while (b != 0) {
    long long q = a / b, x11_cpy = x11, x12_cpy = x12, a_cpy = a;
    x11 = x21, x21 = x11_cpy - q * x21;
    x12 = x22, x22 = x12_cpy - q * x22;
    a = b, b = a_cpy - q * b;
  }
  return std::make_tuple(x11, x12, a);
}

// Input:  integer `a` and `b`.
// Output: (x, gcd(`a`, `b`)) such that `a`x ≡ gcd(`a`, `b`) (mod `b`).
std::pair<long long, long long> inv_gcd(long long a, long long b) {
  long long x11 = 1, x21 = 0;
  while (b != 0) {
    long long q = a / b, x11_cpy = x11, a_cpy = a;
    x11 = x21, x21 = x11_cpy - q * x21;
    a = b, b = a_cpy - q * b;
  }
  return std::make_pair(x11, a);
}

namespace detail {

template <typename ModIntT>
class modular_inverse {
  std::vector<ModIntT> ivs{ModIntT()};

  enum : int { LIM = 1 << 20 };

public:
  modular_inverse() {}
  ModIntT operator()(int k) {
    // assume `ModIntT::mod()` is prime.
    if (k > LIM) return ModIntT(k).inv();
    // preprocess modular inverse from 1 to `k`
    if (int n = static_cast<int>(ivs.size()); n <= k) {
      int nn = n;
      while (nn <= k) nn <<= 1;
      ivs.resize(nn);
      ModIntT v(1);
      for (int i = n; i != nn; ++i) ivs[i] = v, v *= ModIntT(i);
      v = v.inv();
      for (int i = nn - 1; i >= n; --i) ivs[i] *= v, v *= ModIntT(i);
    }
    return ivs[k];
  }
};

} // namespace detail

LIB_END


#line 6 "math\\cra.hpp"

#include <cassert>
#include <numeric>
#include <optional>
#line 12 "math\\cra.hpp"

LIB_BEGIN

namespace detail {

std::optional<std::pair<long long, long long>> cra2(long long a0, long long m0, long long a1,
                                                    long long m1) {
  if (m0 < m1) return cra2(a1, m1, a0, m0);
  auto [x, d]  = inv_gcd(m0, m1);
  auto a1_a0   = a1 - a0; // assume `a0` < `m0` and `a1` < `m1`
  auto a1_a0_d = a1_a0 / d;
  if (a1_a0 != a1_a0_d * d) return {};
  auto m1_d = m1 / d;
  auto k0   = x % m1_d * (a1_a0_d % m1_d) % m1_d;
  if (k0 < 0) k0 += m1_d;
  return std::make_pair(a0 + k0 * m0, m0 * m1_d);
}

} // namespace detail

// Returns (remainder, modular)
std::optional<std::pair<long long, long long>> cra(const std::vector<long long> &a,
                                                   const std::vector<long long> &m) {
  const int n = static_cast<int>(a.size());
  assert(a.size() == m.size());
  auto safe_mod = [](long long a, long long m) { return a %= m, (a < 0 ? a + m : a); };
  long long A = 0, M = 1;
  for (int i = 0; i < n; ++i) {
    auto res = detail::cra2(safe_mod(a[i], m[i]), m[i], A, M);
    if (!res) return {};
    std::tie(A, M) = res.value();
  }
  return std::make_pair(A, M);
}

std::optional<std::pair<int, int>> cra_mod(const std::vector<int> &a, const std::vector<int> &m,
                                           const int modular) {
  const int n = static_cast<int>(a.size());
  assert(a.size() == m.size());
  auto safe_mod = [](int a, int m) {
    if ((a %= m) < 0) a += m;
    return a;
  };
  std::vector<int> m_cpy(m);
  // check conflicts and make coprime
  for (int i = 0; i != n; ++i) {
    auto &&mi = m_cpy[i];
    for (int j = 0; j != i; ++j) {
      auto &&mj = m_cpy[j];
      auto d    = std::gcd(mi, mj);
      if (d == 1) continue;
      if (safe_mod(a[i], d) != safe_mod(a[j], d)) return {};
      mi /= d, mj /= d;
      auto k = std::gcd(mi, d);
      if (k != 1)
        while (d % k == 0) mi *= k, d /= k;
      mj *= d;
    }
  }
  m_cpy.push_back(modular);
  std::vector<int> pp(n + 1, 1), res(n + 1);
  for (int i = 0; i != n; ++i) {
    auto u = (safe_mod(a[i], m_cpy[i]) - res[i]) * inv_gcd(pp[i], m_cpy[i]).first % m_cpy[i];
    if (u < 0) u += m_cpy[i];
    for (int j = i + 1; j <= n; ++j) {
      res[j] = (res[j] + u * pp[j]) % m_cpy[j];
      pp[j]  = static_cast<long long>(pp[j]) * m_cpy[i] % m_cpy[j];
    }
  }
  return std::make_pair(res.back(), pp.back());
}

LIB_END


#line 4 "remote_test\\yuki\\math\\187.0.test.cpp"

#include <algorithm>
#include <iostream>
#line 8 "remote_test\\yuki\\math\\187.0.test.cpp"

int main() {
#ifdef LOCAL
  std::freopen("in", "r", stdin), std::freopen("out", "w", stdout);
#endif
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  std::vector<int> a(n), m(n);
  for (int i = 0; i != n; ++i) std::cin >> a[i] >> m[i];
  auto res = lib::cra_mod(a, m, 1000000007);
  if (res) {
    if (std::all_of(a.begin(), a.end(), [](int n) { return n == 0; })) {
      std::cout << res->second << '\n';
    } else {
      std::cout << res->first << '\n';
    }
  } else {
    std::cout << -1 << '\n';
  }
  return 0;
}
0