結果

問題 No.187 中華風 (Hard)
ユーザー miscalcmiscalc
提出日時 2022-02-15 10:52:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 137 ms / 3,000 ms
コード長 2,812 bytes
コンパイル時間 2,085 ms
コンパイル使用メモリ 206,668 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-11 16:58:23
合計ジャッジ時間 5,217 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,384 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 123 ms
4,380 KB
testcase_03 AC 121 ms
4,376 KB
testcase_04 AC 136 ms
4,380 KB
testcase_05 AC 137 ms
4,376 KB
testcase_06 AC 137 ms
4,380 KB
testcase_07 AC 136 ms
4,380 KB
testcase_08 AC 124 ms
4,380 KB
testcase_09 AC 122 ms
4,380 KB
testcase_10 AC 123 ms
4,376 KB
testcase_11 AC 135 ms
4,380 KB
testcase_12 AC 137 ms
4,380 KB
testcase_13 AC 80 ms
4,380 KB
testcase_14 AC 70 ms
4,376 KB
testcase_15 AC 110 ms
4,376 KB
testcase_16 AC 110 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 105 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 137 ms
4,380 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
//using mint = modint1000000007;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using tlll = tuple<ll, ll, ll>;
constexpr ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll safemod(ll A, ll M) {return (A % M + M) % M;}
ll divfloor(ll A, ll B) {if (B < 0) {return divfloor(-A, -B);} return (A - safemod(A, B)) / B;}
ll divceil(ll A, ll B) {if (B < 0) {return divceil(-A, -B);} return divfloor(A + B - 1, B);}
template<class T> void unique(vector<T> &V) {V.erase(unique(V.begin(), V.end()), V.end());}
template<class T> void sortunique(vector<T> &V) {sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end());}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)

ll modinv(ll a, ll m)
{
  ll b = m, x = 1, y = 0;
  while (b > 0)
  {
    ll q = a / b, r = a - q * b, s = x - q * y;
    a = b, b = r;
    x = y, y = s;
  }
  return (x % m + m) % m;
}

ll precrt(vector<ll> &R, vector<ll> &M, ll md)
{
  ll N = R.size();
  for (ll i = 0; i < N; i++)
  {
    for (ll j = i + 1; j < N; j++)
    {
      ll g = gcd(M.at(i), M.at(j));

      if (R.at(i) % g != R.at(j) % g)
        return -1;

      M.at(i) /= g, M.at(j) /= g;

      ll gi = gcd(M.at(i), g), gj = g / gi;
      do
      {
        g = gcd(gi, gj);
        gi *= g, gj /= g;
      } while (g > 1);

      M.at(i) *= gi, M.at(j) *= gj;
      R.at(i) %= M.at(i), R.at(j) %= M.at(j);
    }
  }
  ll res = 1;
  for (ll i = 0; i < N; i++)
  {
    res *= M.at(i), res %= md;
  }
  return res;
}

ll modcrt(vector<ll> &R, vector<ll> &M, ll md)
{
  ll N = R.size();
  assert(M.size() == N);

  vector<ll> X(N), L(N);
  ll l = M.at(0), x = R.at(0) % l;
  for (ll i = 1; i < N; i++)
  {
    X.at(i) = x % M.at(i);
    L.at(i) = l % M.at(i);
  }
  x %= md, l %= md;
  for (ll i = 1; i < N; i++)
  {
    ll xi = X.at(i), li = L.at(i);
    ll mi = M.at(i), ri = R.at(i) % mi;
    ll t = safemod((ri - xi) * modinv(li, mi), mi);
    for (ll j = i + 1; j < N; j++)
    {
      X.at(j) += t * L.at(j) % M.at(j);
      if (X.at(j) >= M.at(j))
        X.at(j) -= M.at(j);
      L.at(j) *= mi, L.at(j) %= M.at(j);
    }
    x += t * l % md;
    if (x >= md)
      x -= md;
    l *= mi, l %= md;
  }
  return x;
}

int main()
{
  ll N;
  cin >> N;
  vector<ll> X(N), Y(N);
  for (ll i = 0; i < N; i++)
  {
    cin >> X.at(i) >> Y.at(i);
  }

  const ll MOD = 1000000007;

  ll lcm = precrt(X, Y, MOD);
  if (lcm == -1)
    FINALANS(-1);
  if (X == vector<ll>(N, 0))
    FINALANS(lcm);
  
  ll ans = modcrt(X, Y, MOD);
  cout << ans << endl;
}
0