結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー kura197
提出日時 2021-07-08 11:19:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,474 bytes
コンパイル時間 2,333 ms
コンパイル使用メモリ 197,704 KB
最終ジャッジ日時 2025-01-22 18:07:54
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define MOD(a, m) ((a % m + m) % m)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

// 負の数にも対応した mod
// 例えば -17 を 5 で割った余りは本当は 3 (-17 ≡ 3 (mod. 5))
// しかし単に -17 % 5 では -2 になってしまう
inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

// 拡張 Euclid の互除法
// ap + bq = gcd(a, b) となる (p, q) を求め、d = gcd(a, b) をリターンします
//
// ## TODO : 要確認
// ## A = a*x % b を満たすxを求める 
// A = a*x % b --> A + b*y = a*x -->  a*x - b*y = A
// ## ax + by = Aを満たす一般解(x, y)を求める
// auto d = extGcd(a, b, p, q);
// if(A % d != 0) continue;
// p *= A/d, q *= A/d;
// (x, y) = (p + k * (b/d), q - k * (a/d));
//
// (x >= 0となる解)
// x = mod(p, b/d);
// ll k = (p-x) / (b/d):
// y = q - k * (a/d);
long long extGcd(long long a, long long b, long long &p, long long &q) {  
    if (b == 0) { p = 1; q = 0; return a; }  
    long long d = extGcd(b, a%b, q, p);  
    q -= a/b * p;  
    return d;  
}

// 中国剰余定理
// x % m1 == b1 && x % m2 == b2であるxを計算.
// リターン値を (r, m) とすると解は x ≡  r (mod m) (x % m == r)
// 解なしの場合は (0, -1) をリターン
pair<long long, long long> ChineseRem(long long b1, long long m1, long long b2, long long m2) {
  long long p, q;
  long long d = extGcd(m1, m2, p, q); // p is inv of m1/d (mod. m2/d)
  if ((b2 - b1) % d != 0) return make_pair(0, -1);
  long long m = m1 * (m2/d); // lcm of (m1, m2)
  long long tmp = (b2 - b1) / d * p % (m2/d);
  long long r = mod(b1 + m1 * tmp, m);
  return make_pair(r, m);
}

int main(){
    vector<ll> X(3), Y(3);
    REP(i,3)
        cin >> X[i] >> Y[i];

    auto [r0, m0] = ChineseRem(X[0], Y[0], X[1], Y[1]);
    if(m0 == -1){
        cout << -1 << endl;
        return 0;
    }

    auto [r1, m1] = ChineseRem(r0, m0, X[2], Y[2]);
    if(m1 == -1){
        cout << -1 << endl;
        return 0;
    }

    if(r1 == 0)
        r1 += m1;

    cout << r1 << endl;
    return 0;
}
0