結果

問題 No.186 中華風 (Easy)
ユーザー HIcoderHIcoder
提出日時 2023-06-07 19:24:07
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,849 bytes
コンパイル時間 760 ms
コンパイル使用メモリ 89,572 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-28 17:43:58
合計ジャッジ時間 1,969 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘std::tuple<long long int, long long int, long long int> ext_gcd(ll, ll)’ 内:
main.cpp:28:10: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   28 |     auto [g,x,y]=ext_gcd(b,a%b);
      |          ^
main.cpp: 関数 ‘std::pair<long long int, long long int> chinese_rem(ll, ll, ll, ll)’ 内:
main.cpp:77:10: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   77 |     auto [d,p,q] = ext_gcd(m1,m2);
      |          ^
main.cpp: 関数 ‘std::pair<long long int, long long int> chinese_rem2(const std::vector<long long int>&, const std::vector<long long int>&)’ 内:
main.cpp:152:14: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  152 |         auto [c,flag]=chinese_rem(x,M,b[i],m[i]);
      |              ^

ソースコード

diff # 

//
#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<numeric>
#include<queue>
#include<cmath>
#include<deque>
#include<cassert>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const ll INF=1LL<<60;

//ax+by=gcd(a,b)
tuple<ll,ll,ll> ext_gcd(ll a,ll b){
    //cout<<"a="<<a<<",b="<<b<<endl;

    if(b==0){
        //a*1+b*0 = a
        return make_tuple(a,1,0);
    }
    auto [g,x,y]=ext_gcd(b,a%b);
    //cout<<"g="<<g<<",x="<<x<<",y="<<y<<endl;

    return make_tuple(g,y,x-(a/b)*y);

    
}

/*
ll chinese_rem(ll b1,ll m1,ll b2, ll m2){
    
    //d=m1*p+m2*q
    auto [d,p,q] = ext_gcd(m1,m2);

    //cout<<"d="<<d<<",p="<<p<<",q="<<q<<endl;

    ll lcm=(m1/d)*m2;
    
    ll c=(b2-b1)/d;
    c%=lcm;

    if(b2<b1){
        c*=(-1);
    }

    ll t=m1*c%lcm;

    p%=lcm;

    if(p<0){
        
        p+=lcm;
        p%=lcm;
    }
    t*=p;//pが負の数の可能性があるので
    t%=lcm;

    ll x=b1+t;
    x%=lcm;

    return x;
};
*/



pair<ll,ll> chinese_rem(ll b1,ll m1,ll b2, ll m2){
    
    //d=m1*p+m2*q
    auto [d,p,q] = ext_gcd(m1,m2);


    ll lcm=(m1/d)*m2;
    
    if((b2-b1)%d !=0){
        //(r,m)  = r (mod m)
        return make_pair(0,-1);
    }

    ll c=(b2-b1)/d;
   
   
    c*=p;

    c%=(m2/d);
    c*=m1;
    c%=lcm;

    ll x=b1+c;
    x%=lcm;
    x+=lcm;
    x%=lcm;

    return make_pair(x,lcm);
};



ll gcd(ll x,ll y){
    return y==0?x:gcd(y,x%y);
}

ll lcm(ll x,ll y){

    return x/gcd(x,y)*y;
}

/*
ll chinese_rem2(const vector<ll>& b,const vector<ll>& m){

    assert(b.size()==m.size());
    int n=b.size();

    ll m0=1;
    ll x=0;
    ll lcmm=1;
    for(int i=0;i<n;i++){
        x=chinese_rem(x,lcmm,b[i],m[i]);
        
        lcmm=lcm(lcmm,m[i]);
        x%=lcmm;
        
        if(x<0){
            x+=lcmm;
            x%=lcmm;
        }
        x%=lcmm;
        
    }

    cout<<"lcmm="<<lcmm<<endl;
    return x%lcmm;
}
*/

pair<ll,ll> chinese_rem2(const vector<ll>& b,const vector<ll>& m){

    assert(b.size()==m.size());
    int n=b.size();

    ll x=0;
    ll M=1;
    for(int i=0;i<n;i++){
        
        auto [c,flag]=chinese_rem(x,M,b[i],m[i]);
        if(flag==-1){
            return make_pair(0,-1);
        }

        M=lcm(M,m[i]);
        x=c;
        
    }
    // x=x%M+M;
    // x%=M;
    //cout<<"lcmm="<<lcmm<<endl;
    return make_pair((x%M + M)%M ,M);
}


int main(){

    //cout<<chinese_rem(2,3,3,5)<<endl;
    vector<ll> b(3);
    vector<ll> m(3);

    for(int i=0;i<3;i++){
        cin>>b[i]>>m[i];
    }

    if(b[0]==0 && b[1]==0 && b[2]==0){
        cout<<lcm(lcm(m[0],m[1]),m[2])<<endl;
        return 0;
    }

    auto ans=chinese_rem2(b,m);

    if(ans.second==-1){
        cout<<-1<<endl; 
    }else{
  
        cout<<ans.first<<endl;
    }
}
0