結果

問題 No.187 中華風 (Hard)
ユーザー GOTKAKOGOTKAKO
提出日時 2024-03-22 02:23:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 134 ms / 3,000 ms
コード長 1,882 bytes
コンパイル時間 3,076 ms
コンパイル使用メモリ 207,404 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-03-22 02:24:02
合計ジャッジ時間 5,288 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 118 ms
6,676 KB
testcase_03 AC 118 ms
6,676 KB
testcase_04 AC 133 ms
6,676 KB
testcase_05 AC 134 ms
6,676 KB
testcase_06 AC 132 ms
6,676 KB
testcase_07 AC 133 ms
6,676 KB
testcase_08 AC 120 ms
6,676 KB
testcase_09 AC 119 ms
6,676 KB
testcase_10 AC 121 ms
6,676 KB
testcase_11 AC 134 ms
6,676 KB
testcase_12 AC 133 ms
6,676 KB
testcase_13 AC 72 ms
6,676 KB
testcase_14 AC 65 ms
6,676 KB
testcase_15 AC 105 ms
6,676 KB
testcase_16 AC 107 ms
6,676 KB
testcase_17 AC 2 ms
6,676 KB
testcase_18 AC 2 ms
6,676 KB
testcase_19 AC 2 ms
6,676 KB
testcase_20 AC 102 ms
6,676 KB
testcase_21 AC 2 ms
6,676 KB
testcase_22 AC 133 ms
6,676 KB
testcase_23 AC 2 ms
6,676 KB
testcase_24 AC 2 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

long long PreGarner(vector<long long> &B,vector<long long> &M,long long MOD){
    long long ret = 1;
    for(int i=0; i<B.size(); i++) for(int k=i+1; k<B.size(); k++){
        long long g = gcd(M.at(i),M.at(k));
        if(B.at(i)%g != B.at(k)%g) return -1;
        M.at(i) /= g; M.at(k) /= g;
        long long g1 = gcd(M.at(i),g),g2 = g/g1;
        while(true){
            g = gcd(g1,g2);
            if(g == 1) break;
            g1 *= g; g2 /= g;
        } 
        M.at(i) *= g1,M.at(k) *= g2;
        B.at(i) %= M.at(i),B.at(k) %= M.at(k);
    }
    for(auto &m : M) ret = ret*m%MOD;
    return ret; //return lcm(m1,m2,...,mn).
}
long long extgcd(long long a, long long b, long long &x,long long &y){
    if(b == 0){x = 1,y = 0; return a;}
    long long g = extgcd(b,a%b,y,x);
    y -= a/b*x; return g;
}
long long eazymod(long long a,long long m){return (a%m+m)%m;}
long long findinv(long long a,long long m){
    long long x,y; extgcd(a,m,x,y);
    return eazymod(x,m);    
}
long long Garner(vector<long long> &B,vector<long long> &M,long long MOD){
    M.push_back(MOD);
    vector<long long> mulM(M.size(),1),value(M.size(),0);
    for(int i=0; i<B.size(); i++){
        long long t = eazymod((B.at(i)-value.at(i))*findinv(mulM.at(i),M.at(i)),M.at(i));
        for(int k=i+1; k<M.size(); k++){
            value.at(k) = (value.at(k)+t*mulM.at(k))%M.at(k);
            mulM.at(k) = mulM.at(k)*M.at(i)%M.at(k);
        }
    }
    return value.back();
}

int main(){
    int N; cin >> N;
    vector<long long> B,M;
    bool allzero = true;
    while(N--){
        int b,m; cin >> b >> m;
        if(b) allzero = false;
        B.push_back(b); M.push_back(m);
    }
    long long mod = 1e9+7;
    long long lcm = PreGarner(B,M,mod);
    if(lcm == -1 || allzero) cout << lcm << endl;
    else cout << Garner(B,M,mod) << endl;
}
0