#1163469 (C++23) No.3396 ChRisTmas memory

• 問題: No.3396 ChRisTmas memory
• ユーザー: aPNJ777
• 提出日時: 2026-05-08 12:13:21
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 486 ms / 4,000 ms
• コード長: 3,285 bytes
• コンパイル時間: 3,187 ms
• コンパイル使用メモリ: 343,028 KB
• 実行使用メモリ: 7,972 KB
• 最終ジャッジ日時: 2026-05-08 12:13:33
• 合計ジャッジ時間: 10,904 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_1

ファイルパターン	結果
sample	AC * 2
other	AC * 40

ソースコード

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
  while (a) {
    b %= a;
    if (b == 0) return a;
    a %= b;
  }
  return b;
}

long long mod_inv(long long a, long long mod) {
  if (mod == 1) return 0;
  a %= mod;
  long long b = mod, s = 1, t = 0;
  while (1) {
    if (a == 1) return s;
    t -= (b / a) * s;
    b %= a;
    if (b == 1) return t + mod;
    s -= (a / b) * t;
    a %= b;
  }
}

pair<long long, long long> extgcd(long long a, long long b) {
  long long s = a, t = b;
  long long xs = 1, ys = 0, xt = 0, yt = 1;
  while (t > 0) {
    long long u = s / t;
    s -= t * u;
    xs -= xt * u;
    ys -= yt * u;
    swap(s, t);
    swap(xs, xt), swap(ys, yt);
  }
  return {xs, ys};
}

pair<long long, long long> garner(vector<long long> Rem, vector<long long> Mod) {
  assert (Rem.size() == Mod.size());
  int n = int(Mod.size());
  // garner
  long long x = 0, prod = 1;
  for (int i = 0; i < n; i++) {
    if (Mod[i] == 1) continue;
    long long g = gcd(prod, Mod[i]);
    long long c = (Rem[i] + (Mod[i] - x % Mod[i])) % Mod[i];
    if (c % g) return {-1, -1}; // not exist
    long long m = Mod[i] / g;
    c = (c / g) * mod_inv((prod / g) % m, m) % m;
    x = x + c * prod;
    prod *= m;
    x %= prod;
  }
  return {x, prod};
}

long long garner2(vector<long long> Rem, vector<long long> Mod, long long mod) {
  assert (Rem.size() == Mod.size());
  int n = int(Mod.size());
  // garner
  vector<long long> C(n);
  for (int i = 0; i < n; i++) {
    long long x = 0, prod = 1;
    for (int j = 0; j < i; j++) {
      x = (x + C[j] * prod % Mod[i]) % Mod[i];
      prod = (prod * Mod[j]) % Mod[i];
    }
    long long g = gcd(prod, Mod[i]);
    long long c = (Rem[i] + (Mod[i] - x)) % Mod[i];
    if (c % g) return -1; // not exist
    long long m = Mod[i] / g;
    c = (c / g) * mod_inv((prod / g) % m, m) % m;
    Mod[i] /= g, C[i] = c;
  }
  long long ans = 0, c = 0;
  for (int i = n - 1; i >= 0; i--) ans = ((ans * Mod[i]) % mod + C[i]) % mod, c = max(c, C[i]);
  // 中華風
  if (c == 0) {
    ans = 1;
    for (int i = 0; i < n; i++) ans = (ans * Mod[i]) % mod;
  }
  return ans;
}

void solve() {
  int Q;
  cin >> Q;
  vector<long long> M, R;
  int n = 0;
  vector<long long> C;
  for (int t = 0; t < Q; t++) {
    int q;
    cin >> q;
    if (q == 1) {
      long long m, r;
      cin >> m >> r;
      long long x = 0, prod = 1;
      for (int j = 0; j < n; j++) {
        x = (x + C[j] * prod % m) % m;
        prod = (prod * M[j]) % m;
      }
      long long g = gcd(prod, m);
      long long c = (r + (m - x)) % m;
      if (c % g) {
        M.push_back(1), C.push_back(-1), n++;
        continue;
      }
      m /= g;
      c = (c / g) * mod_inv((prod / g) % m, m) % m;
      M.push_back(m), C.push_back(c), n++;
    }
    else if  (q == 2) {
      int k;
      cin >> k;
      for (int i = 0; i < k; i++) M.pop_back(), R.pop_back() ,C.pop_back(), n--;
    }
    else {
      long long m;
      cin >> m;
      long long f = 0, ans = 0;
      for (int i = n - 1; i >= 0; i--) {
        ans = ((ans * M[i]) % m + C[i]) % m;
        if (C[i] == -1) f = 1;
      }
      if (f) ans = -1;
      cout << ans << endl;
    }
  }
}

int main() {
  int T = 1;
  //cin >> T;
  for (int t = 0; t < T; t++) solve();
}