AOJ 2659 箸

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

AOJ 2659 箸

問題概要

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

【操作】
回目の操作では、 個の整数 をうけとって、 を以下の条件を満たすような 以下の最大の正の整数 で置き換える。存在し得ない場合は -1 とする。

• 任意の なる に対して (mod. )

制約

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

解法

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

• (mod. )
• 

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

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