結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー HIcoder
提出日時 2023-06-07 19:16:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,934 bytes
コンパイル時間 1,262 ms
コンパイル使用メモリ 91,200 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 00:22:39
合計ジャッジ時間 2,111 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'std::tuple<long long int, long long int, long long int> ext_gcd(ll, ll)':
main.cpp:27:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   27 |     auto [g,x,y]=ext_gcd(b,a%b);
      |          ^
main.cpp: In function 'll chinese_rem(ll, ll, ll, ll)':
main.cpp:76:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   76 |     auto [d,p,q] = ext_gcd(m1,m2);
      |          ^
main.cpp: In function 'std::pair<long long int, long long int> chinese_rem2(const std::vector<long long int>&, const std::vector<long long int>&)':
main.cpp:149:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  149 |         auto [g,p,q]=ext_gcd(M,m[i]);
      |              ^
main.cpp: In function 'int main()':
main.cpp:180:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  180 |     auto [ans,l]=chinese_rem2(b,m);
      |          ^

ソースコード

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;
};
*/



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;
    
    c*=p;

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

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

    return x;
};



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++){
        
        //p*lcmm + q*m[i]=g
        auto [g,p,q]=ext_gcd(M,m[i]);
        if( (b[i]-x)%g!=0 ) return make_pair(-1,0);
       
        ll c=( ((b[i]-x)/g)*p )%(m[i]/g);
        x+=M*c;
        M*=m[i]/g;

        
    }
    // 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,l]=chinese_rem2(b,m);
    //cout<<"ans="<<ans<<endl;
    cout<<ans<<endl;

    /*
    ll lcmresult=1;
    for(ll c:m){
        lcmresult = lcm(lcmresult,c);
    }
    cout<<"lcmresult="<<lcmresult<<endl;
    */
}
0