けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2659 箸

中国剰余定理ライブラリの verify 用問題の 1 つなん

AOJ 2659 箸

問題概要

箸が最初  N 本あった。また  M 個の正の整数  A_0, A_1, \dots, A_{M-1} が与えられる。 N に対して以下の  D 回の操作を実施したとき、最終的に  N の値がどのようになるかを答えよ ( N が存在し得ない場合には  -1 とせよ)。

【操作】
 d = 0, 1, \dots D-1 回目の操作では、 M 個の整数  R_0, R_1, \dots, R_{M-1} をうけとって、 N を以下の条件を満たすような  N 以下の最大の正の整数  x で置き換える。存在し得ない場合は -1 とする。

  • 任意の  R_i \neq -1 なる  i に対して  x ≡ R_i (mod.  A_i)

制約

  • 1 ≦ N ≦ 1,000,000,000
  • 1 ≦ M ≦ 10
  • 1 ≦ D ≦ 100
  • 2 ≦ Ai ≦ 100

解法

D 回の中国剰余定理を実施する。
各ステップでは、 x の満たすべき条件が

  •  x ≡ r (mod.  M)
  •  x \le N

のように求められるので、 N をこれを満たす最大の正の整数で置き換えていく。

#include <iostream>
#include <vector>
using namespace std;

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

pair<long long, long long> ChineseRem(const vector<long long> &b, const 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 make_pair(0, -1);
    long long tmp = (b[i] - r) / d * p % (m[i]/d);
    r += M * tmp;
    M *= m[i]/d;
  }
  return make_pair(mod(r, M), M);
}

int main() {
  int N, M, D;
  cin >> N >> M >> D;
  vector<long long> A(M);
  for (int i = 0; i < M; ++i) cin >> A[i];
  bool ok = true;
  for (int i = 0; i < D; ++i) {
    vector<long long> b, m;
    for (int j = 0; j < M; ++j) {
      int R; cin >> R;
      if (R != -1) b.push_back(R), m.push_back(A[j]);
    }
    if (b.empty()) continue;

    pair<long long, long long> tmp = ChineseRem(b, m);

    if (tmp.second == -1) ok = false;
    if (N < tmp.first) ok = false;

    N = N - (N - tmp.first) % tmp.second;
  }
  if (ok) cout << N << endl;
  else cout << -1 << endl;
}