結果

問題 No.187 中華風 (Hard)
ユーザー miscalc
提出日時 2022-02-15 10:49:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,722 bytes
コンパイル時間 2,467 ms
コンパイル使用メモリ 199,064 KB
最終ジャッジ日時 2025-01-27 23:14:23
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 16
権限があれば一括ダウンロードができます

ソースコード

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);
      L.at(j) *= mi, L.at(j) %= M.at(j);
    }
    x += t * l % 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0