結果

問題 No.187 中華風 (Hard)
ユーザー kura197kura197
提出日時 2021-07-08 11:32:24
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,023 bytes
コンパイル時間 2,044 ms
コンパイル使用メモリ 203,512 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-14 04:45:56
合計ジャッジ時間 3,496 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 3 ms
4,376 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 3 ms
4,376 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 WA -
testcase_21 AC 1 ms
4,380 KB
testcase_22 WA -
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 1 ms
4,376 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.first %= MOD;
        p.second %= MOD;
        p = ChineseRem(p.first, p.second, B[i], M[i]);
    }
    return p;
}

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

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

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

    r %= MOD;

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