結果
問題 | No.2589 Prepare Integers |
ユーザー | KumaTachiRen |
提出日時 | 2023-12-15 11:54:19 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,409 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 79,180 KB |
最終ジャッジ日時 | 2023-12-16 23:30:25 |
合計ジャッジ時間 | 8,779 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 62 ms
70,524 KB |
testcase_01 | AC | 40 ms
53,588 KB |
testcase_02 | AC | 39 ms
53,588 KB |
testcase_03 | WA | - |
testcase_04 | AC | 528 ms
78,132 KB |
testcase_05 | AC | 399 ms
77,928 KB |
testcase_06 | AC | 353 ms
77,784 KB |
testcase_07 | AC | 359 ms
77,776 KB |
testcase_08 | AC | 278 ms
77,720 KB |
testcase_09 | AC | 258 ms
79,156 KB |
testcase_10 | AC | 259 ms
79,180 KB |
testcase_11 | AC | 261 ms
78,640 KB |
testcase_12 | AC | 373 ms
78,472 KB |
testcase_13 | AC | 347 ms
78,216 KB |
testcase_14 | AC | 316 ms
78,056 KB |
testcase_15 | AC | 338 ms
78,048 KB |
testcase_16 | AC | 325 ms
78,188 KB |
testcase_17 | AC | 269 ms
77,772 KB |
testcase_18 | AC | 270 ms
78,284 KB |
testcase_19 | AC | 271 ms
79,068 KB |
testcase_20 | AC | 268 ms
78,024 KB |
testcase_21 | AC | 259 ms
78,548 KB |
testcase_22 | AC | 263 ms
78,588 KB |
testcase_23 | AC | 264 ms
77,940 KB |
testcase_24 | AC | 264 ms
79,004 KB |
testcase_25 | AC | 270 ms
79,044 KB |
testcase_26 | AC | 267 ms
78,948 KB |
testcase_27 | AC | 216 ms
78,048 KB |
ソースコード
def safe_mod(a, b): c = a % b return c + b if c < 0 else c def ext_gcd(a, b): u, v, x, y = 1, 0, 0, 1 while a > 0: q = b // a x, u = u, x - q * u y, v = v, y - q * v b, a = a, b - q * a return b, x, y def op(a, b): ret, p = 0, 1 while a > 0 or b > 0: ret += (a + b) % k * p a //= k b //= k p *= k return ret def op_pow(a, n): if n == 0: return 0 n = safe_mod(n, k) ret, p = 0, 1 while a > 0: ret += safe_mod(a % k * n, k) * p a //= k p *= k return ret def query1(x): a = [x] for i in reversed(range(log)): g = msd[i] v = [0] * len(a) prod = [0] * (len(a) + 1) for j in range(len(a)): u = a[j] // powk[i] g, prod[j], v[j] = ext_gcd(g, u) prod[j], v[j] = safe_mod(prod[j], k), safe_mod(v[j], k) for j in reversed(range(1, len(a))): prod[j - 1] = safe_mod(prod[j - 1] * prod[j], k) t = op_pow(basis[i], prod[0]) prod[-1] = 1 for j in range(len(a)): t = op(t, op_pow(a[j], v[j] * prod[j + 1] % k)) for j in range(len(a)): a[j] = op(a[j], op_pow(t, -(a[j] // powk[i]) // g)) a.append(op(basis[i], op_pow(t, -msd[i] // g))) if g != k: basis[i] = t msd[i] = g for i in range(log): cnt[i + 1] = cnt[i] * (k // msd[i]) return def query2(x): if x > cnt[log]: print(-1) return ans = 0 for i in reversed(range(log)): ans = op(ans, op_pow(basis[i], (x - 1) // cnt[i] - ans // powk[i] // msd[i])) print(ans) return def query3(x): t, ans = 0, 0 for i in reversed(range(log)): r, d = t // powk[i] % msd[i], (x + 1) // powk[i] % k ans += (d - r + msd[i] - 1) // msd[i] * cnt[i] if (d - r) % msd[i] != 0: break t = op(t, op_pow(basis[i], (d - t // powk[i] % k) // msd[i])) print(ans) return A_MAX = 1e9 k, q = list(map(int, input().split(" "))) powk = [1] while powk[-1] * k <= A_MAX: powk.append(powk[-1] * k) log = len(powk) basis = [0] * log msd = [k] * log cnt = [1] * (log + 1) for _ in range(q): t, x = list(map(int, input().split(" "))) if t == 1: query1(x) if t == 2: query2(x) if t == 3: query3(x)