結果
問題 | No.2589 Prepare Integers |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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';}}}