結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー suibaka
提出日時 2018-04-14 14:49:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 115 ms / 3,000 ms
コード長 3,323 bytes
コンパイル時間 2,560 ms
コンパイル使用メモリ 208,212 KB
最終ジャッジ日時 2025-01-05 10:11:06
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template <typename T>
T extgcd(T a, T b, T& x, T& y) {
    T g = a; x = 1; y = 0;
    if(b != 0) {
        g = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    return g;
}

template <typename T>
T mod_inv(T a, T m) {
    T x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

ll mod_pow(ll a, ll n, const ll mod) {
    ll res = 1;
    ll p = a % mod;
    while(n > 0) {
        if(n & 1) (res *= p) %= mod;
        (p *= p) %= mod;
        n >>= 1;
    }
    return res;
}

ll garner(std::vector<ll> m, std::vector<ll> u, int mod) {
    const int n = m.size();
    std::vector<ll> inv_prod(n);
    {
        for(int i = 1; i < n; ++i) {
            ll prod = m[0] % m[i];
            for(int j = 1; j < i; ++j) {
                prod = (prod * m[j]) % m[i];
            }
            inv_prod[i] = mod_inv(prod, m[i]);
        }
    }

    std::vector<ll> v(n), constants(n);
    v[0] = u[0];
    for(int i = 1; i < n; ++i) {
        ll tmp = v[i - 1];
        for(int j = i - 2; j >= 0; --j) {
            tmp = (tmp * m[j] + v[j]) % m[i];
        }
        v[i] = ((u[i] - tmp) * inv_prod[i]) % m[i];
        if(v[i] < 0) v[i] += m[i];
    }

    ll res = v[n - 1];
    for(int i = n - 2; i >= 0; --i) {
        res = (res * m[i] + v[i]) % mod;
    }
    return res;
}

int main() {
    constexpr int mod = 1e9 + 7;
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    if(count(begin(a), end(a), 0) == n) {
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                const ll g = __gcd(b[i], b[j]);
                b[j] /= g;
            }
        }

        ll ans = 1;
        for(int i = 0; i < n; ++i) {
            ans = (ans * b[i]) % mod;
        }
        cout << ans << endl;
        return 0;
    }

    constexpr int p_max = 40000;
    vector<int> primes;
    vector<bool> is_prime(p_max, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i < p_max; ++i) {
        if(is_prime[i]) {
            primes.push_back(i);
            for(int j = i + i; j < p_max; j += i) {
                is_prime[j] = false;
            }
        }
    }

    set<int> use_p;
    for(int i = 0; i < n; ++i) {
        int v = b[i];
        for(auto p : primes) {
            if(v % p == 0) {
                use_p.insert(p);
                while(v % p == 0) v /= p;
            }
        }
        if(v > 1) use_p.insert(v);
    }

    for(auto p : use_p) {
        vector<ll> tmp(n, 1);
        int max_pos = 0;
        for(int i = 0; i < n; ++i) {
            int v = b[i];
            while(v % p == 0) {
                v /= p;
                tmp[i] *= p;
            }
            if(tmp[max_pos] < tmp[i]) max_pos = i;
        }
        for(int i = 0; i < n; ++i) {
            if(i == max_pos) continue;
            if(a[i] % tmp[i] != a[max_pos] % tmp[i]) {
                cout << -1 << endl;
                return 0;
            }
            b[i] /= tmp[i];
            a[i] %= b[i];
        }
    }

    vector<ll> aa, bb;
    for(int i = 0; i < n; ++i) {
        if(b[i] > 1) {
            aa.push_back(a[i]);
            bb.push_back(b[i]);
        }
    }

    cout << garner(bb, aa, mod) << endl;
}
0