結果

問題 No.187 中華風 (Hard)
ユーザー GOTKAKO
提出日時 2024-03-22 02:00:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,828 bytes
コンパイル時間 2,140 ms
コンパイル使用メモリ 199,904 KB
最終ジャッジ日時 2025-02-20 10:50:22
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 15
権限があれば一括ダウンロードができます

ソースコード

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 findinv(long long a,long long m){
    long long x,y; extgcd(a,m,x,y);
    return (x%m+m)%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 = (((B.at(i)-value.at(i))*findinv(mulM.at(i),M.at(i)))%M.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(i)*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