#1178797 (C++17) No.187 中華風 (Hard)

• 問題: No.187 中華風 (Hard)
• ユーザー: pasta
• 提出日時: 2026-08-25 01:26:05
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 3,837 bytes
• コンパイル時間: 1,422 ms
• コンパイル使用メモリ: 229,416 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-08-25 01:26:47
• 合計ジャッジ時間: 4,461 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
other	AC * 6 WA * 19

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
template <class S> using v = vector<S>;
template <class S> using vv = vector<vector<S>>;
template <class S> using vvv = vector<vector<vector<S>>>;
#define rep(...) overload_rep(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define overload_rep(_1, _2, _3, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); i++)
#define rep3(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>
#define vvvi vector<vector<vector<int>>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define el '\n'
#define sp ' '
#define Yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define NO cout<<"NO"<<endl
template<class T>
bool chmin(T &a, const T &b){
    if (b < a){ a = b; return true; }
    return false;
}
template<class T>
bool chmax(T &a, const T &b){
    if (b > a){ a = b; return true; }
    return false;
}

using mtup = tuple<int, int, int>;
const int INF = 1e9;
const long long LINF = 1e18;
//const int mod = 998244353;
 const int mod = 1e9 + 7;

ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

ll mod_inv(ll a, ll mod) {
    ll x, y;
    extgcd(a, mod, x, y);
    x %= mod;
    if (x < 0) x += mod;
    return x;
}



//解が大きくなりmodで割った余りを出力するとき
// x % mi = ai をすべて満たす最小の x % modを返す
int CRT(vector<int>& a, vector<int>&m, int mod){
    int n = a.size(), x = 0;
    int Mmod = 1;
    for(int i = 0; i < n; ++i){
        int Mi = 1;
        for(int j = 0; j < i; ++j){
            Mi = (long long)Mi * m[j] % m[i];
        }
        int c = (long long)(a[i] - x) * mod_inv(Mi, m[i]) % m[i];
        x = (x + (long long)c * Mmod % mod) % mod;
        Mmod = (long long) Mmod * m[i] % mod;
    }
    return (x + mod) % mod;
}

//1つの素因数分解
vector<ll> fact(ll n){
    vector<ll> res;
    for(int i = 2; (ll)i * i <= n;){
        if(n % i == 0){
            res.push_back(i);
            n /= i;
            continue;
        }
        ++i;
    }
    if(n > 1) res.push_back(n);
    return res;
}

//a^x mod(p)
int mod_pow(ll a, ll x){
    a %= mod;
    if(a == 0){
        if(x == 0) return 1;
        return 0;
    }
    int res = 1;
    while(x){
        if(x & 1){
            res = res * a % mod;
        }
        a = a * a % mod;
        x >>= 1;
    }
    return res;
}

int main(){
    //高速化
    //ここから

    int n; cin >> n;
    vi x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];
    map<int, pii> mp;
    rep(i, n){
        vll a = fact(y[i]);
        sort(all(a));
        a.push_back(-1);
        int m = 1;
        rep(j, a.size() - 1){
            if(a[j] == a[j + 1]) m++;
            else{
                if(mp.count(a[j])){
                    auto [md, k] = mp[a[j]];
                    int p = mod_pow(a[j], min(k, m));
                    if(md % p != x[i] % p){
                        cout << - 1 << el;
                        return 0;
                    }else if(m > k){
                        mp[a[j]] = {x[i], m};
                    }
                }else{
                    mp[a[j]] = {x[i], m};
                }
                m = 1;
            }
        }
    }
    vi a, md;
    for(auto [key, vl]:mp){
        int tmp = mod_pow(key, vl.second);
        a.push_back(vl.first % tmp);
        md.push_back(tmp);
    }
    cout << CRT(a, md, mod) << el;

}
/*
cppt
cppt_ge
seg, bit, uf

g++ main.cpp -O2 -std=c++17
./a.out

*/