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

• 問題: No.187 中華風 (Hard)
• ユーザー: pasta
• 提出日時: 2026-08-25 02:44:42
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 101 ms / 3,000 ms
• コード長: 4,153 bytes
• コンパイル時間: 1,543 ms
• コンパイル使用メモリ: 225,560 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-25 02:44:48
• 合計ジャッジ時間: 4,153 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
other	AC * 25

ソースコード

#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();
    vector<int> c(n);
    for(int i = 0; i < n; ++i){
        int xi = 0, Mi = 1;
        for(int j = 0; j < i; ++j){
            xi = (xi + (ll)c[j] * Mi) % m[i];
            Mi = (ll)Mi * m[j] % m[i];
        }

        c[i] = (ll)(a[i] - xi) * mod_inv(Mi, m[i]) % m[i];
        c[i] = (c[i] + m[i]) % m[i];
    }

    //x = c0 + c1m0 + c2m0m1 +...
    int M = 1, res = 0;
    for(int i = n - 1; i >= 0; --i){
        res = ((ll)res * m[i] % mod + c[i]) % mod;
    }
    return res;
}

//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;
}

int solve(const vector<int> &x, const vector<int> &y, int mod){
    int n = x.size();
    map<int, pair<int,int>> mp;
    for(int i = 0; i < n; ++i){
        auto a = fact(y[i]);
        a.push_back(-1);    //番兵
        int mod = 1;
        for(int j = 0; j < a.size() - 1; ++j){
            mod *= a[j];
            if(a[j] != a[j + 1]){
                if(mp.count(a[j])){
                    auto [r, oldmod] = mp[a[j]];
                    int p = min(mod, oldmod);
                    if(r % p != x[i] % p){
                        //矛盾するため解なし
                        return -1;
                    }else if(mod > oldmod){
                        //制約が厳しい方に更新する
                        mp[a[j]] = {x[i] % mod, mod};
                    }
                }else{
                    mp[a[j]] = {x[i], mod};
                }
                mod = 1;
            }
        }
    }

    //正整数の最小値を求める制約の場合
    //満たす数が0でも許される場合は不要
    if(*max_element(x.begin(), x.end()) == 0){
        ll res = 1;
        for(auto [key, vl]:mp) res = res * vl.second % mod;
        return res;
    }

    vector<int> a, md;
    for(auto [key, vl]:mp){
        a.push_back(vl.first);
        md.push_back(vl.second);
    }
    return CRT(a, md, mod);
}
int main(){
    //高速化
    //ここから

    int n; cin >> n;
    vi x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];
    cout << solve(x, y, mod) << el;

}
/*
cppt
cppt_ge
seg, bit, uf

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

*/