#938812 (C++23) No.2589 Prepare Integers

提出ソース

結果

問題	No.2589 Prepare Integers
ユーザー	Kude
提出日時	2023-12-17 08:45:16
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	69 ms / 2,000 ms
コード長	5,607 bytes
コンパイル時間	3,757 ms
コンパイル使用メモリ	288,332 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-27 07:58:46
合計ジャッジ時間	5,143 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	69 ms 6,944 KB
testcase_05	AC	35 ms 6,944 KB
testcase_06	AC	22 ms 6,944 KB
testcase_07	AC	19 ms 6,944 KB
testcase_08	AC	8 ms 6,940 KB
testcase_09	AC	6 ms 6,944 KB
testcase_10	AC	7 ms 6,940 KB
testcase_11	AC	7 ms 6,940 KB
testcase_12	AC	26 ms 6,940 KB
testcase_13	AC	21 ms 6,940 KB
testcase_14	AC	16 ms 6,944 KB
testcase_15	AC	17 ms 6,944 KB
testcase_16	AC	15 ms 6,944 KB
testcase_17	AC	10 ms 6,940 KB
testcase_18	AC	8 ms 6,940 KB
testcase_19	AC	7 ms 6,944 KB
testcase_20	AC	6 ms 6,940 KB
testcase_21	AC	7 ms 6,940 KB
testcase_22	AC	7 ms 6,940 KB
testcase_23	AC	7 ms 6,940 KB
testcase_24	AC	7 ms 6,944 KB
testcase_25	AC	7 ms 6,944 KB
testcase_26	AC	7 ms 6,940 KB
testcase_27	AC	5 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード