結果

問題 No.2589 Prepare Integers
ユーザー KudeKude
提出日時 2023-12-17 05:34:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,762 bytes
コンパイル時間 3,633 ms
コンパイル使用メモリ 286,160 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-27 07:57:12
合計ジャッジ時間 5,324 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 1 WA * 14 RE * 9
権限があれば一括ダウンロードができます

ソースコード

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 [g, x] = internal::inv_gcd(v.back(), k);
for (int& vi : v) vi = ll(vi * x) % k;
assert(v.back() == g);
};
rep(i, ssize(basis)) {
auto& b = basis[i];
if (ssize(v) > ssize(b)) {
normalize(v);
basis.insert(basis.begin() + i, move(v));
v = {};
break;
}
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;
}
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();
}
if (!v.empty()) {
normalize(v);
basis.emplace_back(move(v));
}
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 = 0;
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';
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0