結果
問題 | No.2589 Prepare Integers |
ユーザー | KumaTachiRen |
提出日時 | 2023-12-16 21:55:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 492 ms / 2,000 ms |
コード長 | 2,500 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 79,012 KB |
最終ジャッジ日時 | 2023-12-16 23:30:43 |
合計ジャッジ時間 | 8,234 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 60 ms
70,524 KB |
testcase_01 | AC | 38 ms
53,460 KB |
testcase_02 | AC | 38 ms
53,460 KB |
testcase_03 | AC | 38 ms
53,460 KB |
testcase_04 | AC | 492 ms
78,016 KB |
testcase_05 | AC | 383 ms
77,804 KB |
testcase_06 | AC | 337 ms
77,656 KB |
testcase_07 | AC | 337 ms
77,776 KB |
testcase_08 | AC | 259 ms
78,404 KB |
testcase_09 | AC | 245 ms
79,000 KB |
testcase_10 | AC | 238 ms
79,012 KB |
testcase_11 | AC | 244 ms
78,592 KB |
testcase_12 | AC | 340 ms
78,348 KB |
testcase_13 | AC | 322 ms
77,952 KB |
testcase_14 | AC | 291 ms
77,916 KB |
testcase_15 | AC | 312 ms
77,920 KB |
testcase_16 | AC | 298 ms
78,120 KB |
testcase_17 | AC | 246 ms
77,776 KB |
testcase_18 | AC | 259 ms
78,144 KB |
testcase_19 | AC | 257 ms
78,968 KB |
testcase_20 | AC | 251 ms
78,280 KB |
testcase_21 | AC | 239 ms
78,440 KB |
testcase_22 | AC | 247 ms
78,456 KB |
testcase_23 | AC | 247 ms
77,556 KB |
testcase_24 | AC | 245 ms
78,872 KB |
testcase_25 | AC | 250 ms
78,904 KB |
testcase_26 | AC | 247 ms
78,820 KB |
testcase_27 | AC | 201 ms
77,928 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): if x + 1 >= powk[-1]: print(cnt[log]) return 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) powk.append(powk[-1] * k) 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)