結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー HIcoder
提出日時 2023-09-09 11:51:58
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 1,710 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 969 ms
コンパイル使用メモリ 99,960 KB
最終ジャッジ日時 2025-02-16 20:36:36
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<numeric>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const ll INF=1LL<<60;
typedef pair<int,int> P;
typedef pair<int,P> PP;
const ll MOD=1e9+7;


inline long long  mod(long long  a,long long m){
    return (a%m+m)%m;
}


long long  extGcd(long long  a,long long  b,long long& x,long long& y){
    long long  d=a;
    if(b!=0){
        d=extGcd(b,a%b,y,x);
        y-=(a/b)*x;
    }else{
        x=1;y=0;
    }

    return d;
}



// x ≡ bi (mod mi)
// 中国剰余定理
// リターン値を (r, m) とすると解は x ≡ r (mod. m)
// 解なしの場合は (0, -1) をリターン
std::pair<long long, long long> ChineseRem(const std::vector<long long> &b, const std::vector<long long> &m) {
  long long r = 0, M = 1;
  for (int i = 0; i < (int)b.size(); ++i) {
    long long p, q;
    long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
    if ((b[i] - r) % d != 0) return std::make_pair(0, -1);
    long long tmp = (b[i] - r) / d * p % (m[i]/d);
    r += M * tmp;
    M *= m[i]/d;
  }
  return std::make_pair(mod(r, M), M);
}

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


int main(){
    vector<ll> X(3),Y(3);
    for(int i=0;i<3;i++){
        cin>>X[i]>>Y[i];
    }

    if(X[0]==0 && X[1]==0 && X[2]==0){
        ll ans=1;
        for(int i=0;i<3;i++){
            ans=lcm(Y[i],ans);
        }

        cout<<ans<<endl;
        return 0;
    }

    auto [ans,mod]=ChineseRem(X,Y);

    if(mod==-1){
        cout<<-1<<endl;
    }else{
        cout<<ans<<endl;
    }

}
0