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