結果

問題 No.2589 Prepare Integers
ユーザー KudeKude
提出日時 2023-12-17 08:45:16
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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';
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0