結果

問題 No.187 中華風 (Hard)
ユーザー nikutto_nikutto_
提出日時 2019-10-28 22:32:57
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 384 ms / 3,000 ms
コード長 2,713 bytes
コンパイル時間 1,399 ms
コンパイル使用メモリ 165,256 KB
実行使用メモリ 4,352 KB
最終ジャッジ日時 2023-10-12 23:13:11
合計ジャッジ時間 5,912 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,352 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 73 ms
4,352 KB
testcase_03 AC 70 ms
4,348 KB
testcase_04 AC 214 ms
4,352 KB
testcase_05 AC 206 ms
4,352 KB
testcase_06 AC 211 ms
4,348 KB
testcase_07 AC 213 ms
4,352 KB
testcase_08 AC 383 ms
4,348 KB
testcase_09 AC 383 ms
4,352 KB
testcase_10 AC 384 ms
4,348 KB
testcase_11 AC 209 ms
4,352 KB
testcase_12 AC 214 ms
4,352 KB
testcase_13 AC 278 ms
4,352 KB
testcase_14 AC 228 ms
4,348 KB
testcase_15 AC 43 ms
4,348 KB
testcase_16 AC 46 ms
4,352 KB
testcase_17 AC 1 ms
4,348 KB
testcase_18 AC 2 ms
4,352 KB
testcase_19 AC 1 ms
4,348 KB
testcase_20 AC 178 ms
4,348 KB
testcase_21 AC 2 ms
4,348 KB
testcase_22 AC 212 ms
4,352 KB
testcase_23 AC 2 ms
4,352 KB
testcase_24 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

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;
                }
                if(prem<nowm) mcb[p.first]={max(p.second,mcb[p.first].first),x[i]%nowm};
                else mcb[p.first]={max(p.second,mcb[p.first].first),mcb[p.first].second};
            }
            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();
    }
    if(all_of(x.begin(),x.end(),[](ll v){return v==0;})){
        ll res = 1;
        for(auto v:m) res=res*v%MOD;
        cout<<res<<endl;
        return 0;
    }
    ll ret = crt(b,m);
    cout<<crt(b,m)<<endl;
    return 0;
}
0