結果

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

ソースコード

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





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

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

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

}
0