結果

問題 No.2589 Prepare Integers
ユーザー KudeKude
提出日時 2023-12-17 08:45:16
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 68 ms / 2,000 ms
コード長 5,607 bytes
コンパイル時間 3,791 ms
コンパイル使用メモリ 288,016 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2023-12-17 08:45:22
合計ジャッジ時間 5,542 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 68 ms
6,676 KB
testcase_05 AC 35 ms
6,676 KB
testcase_06 AC 22 ms
6,676 KB
testcase_07 AC 19 ms
6,676 KB
testcase_08 AC 8 ms
6,676 KB
testcase_09 AC 6 ms
6,676 KB
testcase_10 AC 6 ms
6,676 KB
testcase_11 AC 6 ms
6,676 KB
testcase_12 AC 26 ms
6,676 KB
testcase_13 AC 20 ms
6,676 KB
testcase_14 AC 16 ms
6,676 KB
testcase_15 AC 17 ms
6,676 KB
testcase_16 AC 15 ms
6,676 KB
testcase_17 AC 9 ms
6,676 KB
testcase_18 AC 8 ms
6,676 KB
testcase_19 AC 8 ms
6,676 KB
testcase_20 AC 6 ms
6,676 KB
testcase_21 AC 6 ms
6,676 KB
testcase_22 AC 6 ms
6,676 KB
testcase_23 AC 7 ms
6,676 KB
testcase_24 AC 6 ms
6,676 KB
testcase_25 AC 6 ms
6,676 KB
testcase_26 AC 6 ms
6,676 KB
testcase_27 AC 5 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

tuple<int, int, int, int, int> gcd_coeff(int x, int y) {
  int a = 1, b = 0, c = 0, d = 1;
  while (y) {
    int q = x / y;
    x = x % y;
    a -= c * q;
    b -= d * q;
    swap(x, y);
    swap(a, c);
    swap(b, d);
  }
  return {x, a, b, c, d};
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int k, q;
  cin >> k >> q;
  VVI basis;
  VL right_cnt{1};
  rep(_, q) {
    int t;
    ll x;
    cin >> t >> x;
    if (t == 1) {
      VI v;
      while (x) {
        v.emplace_back(x % k);
        x /= k;
      }
      auto normalize = [&](VI& v) {
        assert(!v.empty() && v.back());
        auto [g1, x1] = internal::inv_gcd(v.back(), k);
        int k1 = k / g1;
        // x1 + i * k1, k
        int kk = k;
        int g_acc = 1;
        for (int g = gcd(k1, kk); g > 1; g = gcd(g_acc, kk)) {
          kk /= g;
          g_acc *= g;
        }
        auto [g2, x2] = internal::inv_gcd(k1, kk);
        assert(g2 == 1);
        // x1 + i * k1 = 1 (mod kk)
        int i = ll(1 - x1) * x2 % kk;
        if (i < 0) i += kk;
        int x = (x1 + (ll)i * k1) % k;
        for (int& vi : v) vi = ll(vi) * x % k;
        assert(v.back() == g1);
      };
      rep(i, ssize(basis)) {
        while (ssize(v) > ssize(basis[i])) {
          normalize(v);
          basis.insert(basis.begin() + i, v);
          i++;
          int x = k / v.back();
          rep (i, ssize(v)) v[i] = (ll)v[i] * x % k;
          assert(v.back() == 0);
          while (!v.empty() && v.back() == 0) v.pop_back();
        }
        auto& b = basis[i];
        if (ssize(v) < ssize(b)) continue;
        assert(ssize(v) == ssize(b));
        int& vv = v.back();
        int& bv = b.back();
        if (vv % bv) {
          auto [g, xa, xb, ya, yb] = gcd_coeff(vv, bv);
          rep(i, ssize(b)) {
            int pv = v[i], pb = b[i];
            b[i] = ((ll)xa * pv + (ll)xb * pb) % k;
            v[i] = ((ll)ya * pv + (ll)yb * pb) % k;
            if (b[i] < 0) b[i] += k;
            if (v[i] < 0) v[i] += k;
          }
          assert(bv == g);
        }
        assert(vv % bv == 0);
        int x = vv / bv;
        rep(i, ssize(v)) {
          v[i] = v[i] - ll(x) * b[i] % k;
          if (v[i] < 0) v[i] += k;
        }
        assert(v.back() == 0);
        while (!v.empty() && v.back() == 0) v.pop_back();
      }
      while (!v.empty()) {
        normalize(v);
        basis.emplace_back(v);
        int x = k / v.back();
        rep (i, ssize(v)) v[i] = ((ll)v[i] * x) % k;
        assert(v.back() == 0);
        while (!v.empty() && v.back() == 0) v.pop_back();
      }
      right_cnt.resize(ssize(basis) + 1);
      right_cnt.back() = 1;
      rrep(i, ssize(basis)) right_cnt[i] = right_cnt[i+1] * (k / basis[i].back());
    } else if (t == 2) {
      x--;
      if (x >= right_cnt[0]) {
        cout << -1 << '\n';
        continue;
      }
      int sz = ssize(basis);
      int ans[30]{};
      rep(i, sz) {
        const auto& b = basis[i];
        ll unit = right_cnt[i + 1];
        int skip = min<ll>(x / unit, k / b.back());
        x -= (ll)skip * unit;
        int& vv = ans[ssize(b) - 1];
        int bv = b.back();
        int now = vv / bv;
        int d = skip - now;
        if (d < 0) d += k;
        rep(i, ssize(b)) ans[i] = (ans[i] + (ll)b[i] * d) % k;
      }
      assert(x == 0);
      ll v = 0;
      rrep(i, 30) v = (k * v + ans[i]);
      cout << v << '\n';
    } else {
      assert(t == 3);
      ll ans = basis.empty();
      x++;
      VI v;
      while (x) {
        v.emplace_back(x % k);
        x /= k;
      }
      int now[30]{};
      rep(i, ssize(basis)) {
        const auto& b = basis[i];
        int cmp = 0;
        while (ssize(v) > ssize(b)) {
          int i = ssize(v) - 1;
          if (now[i] < v[i]) {
            cmp = -1;
            break;
          } else if (now[i] > v[i]) {
            cmp = 1;
            break;
          }
          v.pop_back();
        }
        if (cmp) {
          if (cmp == -1) ans += right_cnt[i];
          break;
        }
        int vv = ssize(v) == ssize(b) ? v.back() : 0;
        int bv = b.back();
        int& nv = now[ssize(b) - 1];
        if (nv >= bv) {
          int x = (k + nv % bv - nv) / bv;
          rep(i, ssize(b)) now[i] = (now[i] + (ll)x * b[i]) % k;
          assert(nv < bv);
        }
        int diff = vv - nv;
        if (diff < 0) break;
        ans += (vv - nv + bv - 1) / bv * right_cnt[i+1];
        if (diff % bv) break;
        int x = diff / bv;
        rep(i, ssize(b)) now[i] = (now[i] + (ll)x * b[i]) % k;
        assert(nv == vv);
        if (i == ssize(basis) - 1) {
          while (!v.empty()) {
            int i = ssize(v) - 1;
            if (now[i] != v[i]) {
              ans += now[i] < v[i];
              break;
            }
            v.pop_back();
          }
        }
      }
      cout << ans << '\n';
    }
  }
}
0