結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー goodbaton
提出日時 2019-10-30 11:26:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 213 ms / 3,000 ms
コード長 3,117 bytes
コンパイル時間 1,024 ms
コンパイル使用メモリ 105,488 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 21:46:05
合計ジャッジ時間 4,790 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

// {a, {b, c}} : a = gcd(p, q) = bp + cq
pair<ll,pair<ll,ll>> ext_gcd(ll p, ll q) {
  if (q == 0) return {p, {1, 0}};
  auto r = ext_gcd(q, p%q);
  return {r.first, {r.second.second, r.second.first - p/q*r.second.second}};
}


// GCC __gcd(long long A, long long B)

ll gcd(ll a, ll b){
  if(a == 0) return b;
  return gcd(b%a, a);
}

ll lcm(ll a, ll b){
  return a / gcd(a, b) * b;
}


/* Garner */
// modsは互いに素

ll Garner(vector<ll> b, vector<ll> mods, ll MOD) {
  mods.push_back(MOD);
  vector<ll> coeffs((int)mods.size(), 1);
  vector<ll> constants((int)mods.size(), 0);
  for (int i = 0; i < (int)b.size(); i++) {
    ll m = mods[i];
    ll s = (ext_gcd(coeffs[i], m).second.first % m + m) % m;
    ll t = ((b[i] - constants[i]) * s % m + m) % m;
    for (int j = i+1; j < (int)mods.size(); j++) {
      constants[j] = (constants[j] + t * coeffs[j]) % mods[j];
      coeffs[j] = (coeffs[j] * m) % mods[j];
    }
  }
  return constants.back();
}

//破壊的
ll preGarner(vector<ll> &b, vector<ll> &mods, ll MOD) {
  ll res = 1;
  for (int i = 0; i < (int)b.size(); i++) {
    for (int j = 0; j < i; j++) {
      ll g = gcd(mods[i], mods[j]);
      if ((b[i] - b[j]) % g != 0) return -1;
      mods[i] /= g;
      mods[j] /= g;
      ll gi = gcd(mods[i], g);
      ll gj = g / gi;
      do {
        g = gcd(gi, gj);
        gi *= g; gj /= g;
      } while (g != 1);
      mods[i] *= gi; mods[j] *= gj;
      b[i] %= mods[i]; b[j] %= mods[j];
    }
  }
  for (int i = 0; i < (int)b.size(); ++i)
    res = res * mods[i] % MOD;
  return res;
}

// ll lcm = preGarner(x, y, mod);
// if (lcm == -1) //NG; else if (forall x is 0) //lcm or 0 else ans = Garner(x, y);

int main(){
  int N;
  vector<ll> mods, vals;
  bool zeroFlag = true;

  cin >> N;

  for (int i=0; i<N; i++) {
    ll x, y;
    cin >> x >> y;
    vals.push_back(x);
    mods.push_back(y);
    zeroFlag &= x == 0;
  }

  ll lcm = preGarner(vals, mods, mod);

  debug(vals);
  debug(mods);

  if (lcm == -1) {
    puts("-1");
  } else if (zeroFlag) {
    printf("%lld\n", lcm);
  } else {
    printf("%lld\n", Garner(vals, mods, mod));
  }

  return 0;
}
0