結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー nikutto_
提出日時 2019-10-28 22:18:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,436 bytes
コンパイル時間 1,695 ms
コンパイル使用メモリ 177,100 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 21:20:41
合計ジャッジ時間 6,006 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

// verify https://yukicoder.me/problems/no/186
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using ll=long long;

ll extGcd(ll a,ll b,ll& p,ll &q){
    if(b==0) {p=1; q=0; return a;}
    ll d = extGcd(b,a%b,q,p);
    q -= a/b * p;
    return d;
}using namespace std;

using ll=long long;
const ll MOD=1e9+7;

// Note that mod may not be prime.
ll modInv(ll a,ll mod){
    long long x,y;
    extGcd(a,mod,x,y);
    return (x%mod+mod)%mod;
}

// all m must be coprime each other.
// O(K^2), where K is size of b and m
// return 
ll crt(vector<ll> b,vector<ll> m){
    int k=b.size();
    vector<ll> t(k);
    ll r;
    auto calc=[&](int end,ll mod){
        ll sum = 0;
        r=1;
        for(int i=0;i<end;i++){
            sum = (sum + r*t[i])%mod;
            r = r * m[i] % mod;
        }
        return sum;
    };
    for(int i=0;i<k;i++){
        t[i] = (b[i]-calc(i,m[i]))*modInv(r,m[i])%m[i];
        t[i] = (t[i]+m[i])%m[i];
    }
    return (calc(k,MOD)+MOD)%MOD;
}
// modify ll -> __int128
int main(){
    int n;
    cin>>n;
    vector<ll> x(n),y(n);
    for(int i=0;i<n;i++) cin>>x[i]>>y[i];
    map<ll,pair<int,ll>> mcb;
    for(int i=0;i<n;i++){
        map<ll,int> mp;
        ll v=y[i];
        for(ll j=2;j*j<=v;j++){
            if(v%j==0){
                int cnt=0;
                while(v%j==0) cnt++,v/=j;
                mp[j]=cnt;
            }
        }
        if(v>1){
            mp[v]=1;
        }
        for(auto& p:mp){
            if(mcb.count(p.first)){
                ll prem = 1;
                for(int j=0;j<mcb[p.first].first;j++) prem=prem*p.first;
                ll nowm = 1;
                for(int j=0;j<p.second;j++) nowm=nowm*p.first;
                ll mod = min(prem,nowm);
                if(mcb[p.first].second%mod!=x[i]%mod){
                    cout<<-1<<endl;
                    return 0;
                }
                mcb[p.first]={max(p.second,mcb[p.first].first),max(mcb[p.first].second,x[i])};
            }
            else{
                ll tmp=1;
                for(int j=0;j<p.second;j++) tmp=tmp*p.first;
                mcb[p.first]={p.second,x[i]%tmp};
            }
        }
    }
    vector<ll> b,m;
    for(auto& e:mcb){
        b.push_back(e.second.second);
        ll tmp=1;
        for(int i=0;i<e.second.first;i++) tmp*=e.first;
        m.push_back(tmp);
        b.back()%=m.back();
    }
    cout<<crt(b,m)<<endl;
    return 0;
}
0