結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー tokusakurai
提出日時 2021-02-10 20:49:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 143 ms / 3,000 ms
コード長 3,565 bytes
コンパイル時間 2,117 ms
コンパイル使用メモリ 200,928 KB
最終ジャッジ日時 2025-01-18 17:08:49
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

//ユークリッドの互除法を用いた種々の計算
//計算量 gcd, lcm, extgcd, modinv, floor_sum, 中国剰余定理:O(log(max(a, b)))、Garner:O(N^2+N*log(M))

//中国剰余定理 : x ≡ a_1(mod m_1), x ≡ a_2(mod m_2)を満たす最小の非負整数xを求める
//Garner : x ≡ a_i(mod m_i)を満たす最小の非負整数xをMで割った余りを求める

//verified with
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B&lang=ja
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_C&lang=ja
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E&lang=jp
//https://atcoder.jp/contests/practice2/tasks/practice2_c
//https://yukicoder.me/problems/no/186
//https://yukicoder.me/problems/no/187

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

template<typename T>
T gcd(const T &a, const T &b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

template<typename T>
T lcm(const T &a, const T &b) {return a*(b/gcd(a,b));}

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

int mod(const long long &a, const int &m){
    int ret = a%m;
    return ret+(ret < 0? m : 0);
}

int modinv(const int &a, const int &m){ //aとmは互いに素
    int x, y;
    extgcd(a, m, x, y);
    return mod(x, m);
}

template<typename T>
T floor_sum(const T &n, const T &m, T a, T b){ //Σ(floor((a*i+b)/m)) (0<=i<n)
    T ret = (a/m)*(n*(n-1)/2)+(b/m)*n;
    a %= m, b %= m;
    T y = (a*n+b)/m;
    if(y == 0) return ret;
    ret += floor_sum(y, a, m, a*n-(m*y-b));
    return ret;
}

template<typename T>
pair<T, T> Chinese_reminder_theorem(const T &a1, const T &m1, const T &a2, const T &m2){
    T x, y, g = extgcd(m1, m2, x, y);
    if((a2-a1)%g != 0) return make_pair(0, -1);
    T m = m1*(m2/g);
    T tmp = mod(x*((a2-a1)/g), m2/g);
    T a = (m1*tmp+a1) % m;
    return make_pair(a, m);
}

bool prepare_Garner(vector<int> &a, vector<int> &m){ //mの各要素がそれぞれ互いに素とは限らない場合の前処理
    int n = a.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            int g = gcd(m[i], m[j]);
            if((a[i]-a[j])%g != 0) return false;
            m[i] /= g, m[j] /= g;
            int gi = gcd(m[i], g), gj = g/gi;
            do{
                g = gcd(gi, gj);
                gi *= g, gj /= g;
            } while(g > 1);
            m[i] *= gi, m[j] *= gj;
        }
    }
    return true;
}

int Garner(vector<int> a, vector<int> m, const int &M){ //mの各要素はそれぞれ互いに素
    m.push_back(M);
    vector<long long> coeffs(m.size(), 1);
    vector<long long> constants(m.size(), 0);
    for(int k = 0; k < (int)a.size(); k++){
        long long x = a[k]-constants[k], y = modinv(coeffs[k], m[k]);
        long long t = mod(x*y, m[k]);
        for(int i = k+1; i < m.size(); i++){
            constants[i] += t*coeffs[i], constants[i] %= m[i];
            coeffs[i] *= m[k], coeffs[i] %= m[i];
        }
    }
    return constants.back();
}

int main(){
    const int MOD = 1000000007;
    int N; cin >> N;

    vector<int> a(N), m(N);
    for(int i = 0; i < N; i++) cin >> a[i] >> m[i];

    if(!prepare_Garner(a, m)) {cout << -1 << '\n'; return 0;}
    long long l = 1;

    for(int i = 0; i < N; i++) l *= m[i], l %= MOD;
    bool flag = true;
    for(int i = 0; i < N; i++) if(a[i] != 0) flag = false;
    if(flag) {cout << l << '\n'; return 0;}
    
    cout << Garner(a, m, MOD) << '\n';
}
0