結果

問題 No.186 中華風 (Easy)
ユーザー kura197kura197
提出日時 2021-07-08 11:28:48
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,935 bytes
コンパイル時間 1,831 ms
コンパイル使用メモリ 202,732 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-14 04:45:52
合計ジャッジ時間 3,114 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,356 KB
testcase_01 AC 2 ms
4,356 KB
testcase_02 AC 2 ms
4,356 KB
testcase_03 AC 1 ms
4,352 KB
testcase_04 AC 1 ms
4,356 KB
testcase_05 AC 1 ms
4,356 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,356 KB
testcase_08 AC 1 ms
4,356 KB
testcase_09 AC 1 ms
4,352 KB
testcase_10 AC 1 ms
4,352 KB
testcase_11 AC 2 ms
4,360 KB
testcase_12 AC 1 ms
4,356 KB
testcase_13 AC 1 ms
4,352 KB
testcase_14 AC 1 ms
4,356 KB
testcase_15 AC 1 ms
4,356 KB
testcase_16 AC 1 ms
4,356 KB
testcase_17 AC 1 ms
4,356 KB
testcase_18 AC 1 ms
4,352 KB
testcase_19 AC 1 ms
4,356 KB
testcase_20 AC 1 ms
4,352 KB
testcase_21 AC 2 ms
4,360 KB
testcase_22 AC 1 ms
4,356 KB
権限があれば一括ダウンロードができます

ソースコード

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

// ##TODO: 要確認
// 全てのidxに対して、
// x % M[idx] == B[idx] を満たすxを計算.
// リターン値を (r, m) とすると解は x ≡  r (mod m) (x % m == r)
// 解なしの場合は (0, -1) をリターン
pair<long long, long long> ChineseRem(vector<long long>& B, vector<long long> M) {
    assert(B.size() == M.size());
    if(B.size() == 0)
        return make_pair(0, -1);
    if(B.size() == 1)
        return make_pair(B[0], M[0]);

    auto p = ChineseRem(B[0], M[0], B[1], M[1]);
    for(size_t i = 2; i < B.size(); i++){
        if(p.second == -1)
            return p;
        p = ChineseRem(p.first, p.second, B[i], M[i]);
    }
    return p;
}

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

    auto [r, m] = ChineseRem(X, Y);

    if(r == 0)
        r += m;

    cout << r << endl;
    return 0;
}
0