結果

問題 No.2589 Prepare Integers
ユーザー KumaTachiRenKumaTachiRen
提出日時 2023-12-07 17:01:51
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,823 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 79,844 KB
最終ジャッジ日時 2023-12-16 23:30:23
合計ジャッジ時間 8,628 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
70,524 KB
testcase_01 AC 37 ms
53,588 KB
testcase_02 AC 38 ms
53,588 KB
testcase_03 WA -
testcase_04 AC 560 ms
78,912 KB
testcase_05 AC 424 ms
78,112 KB
testcase_06 AC 374 ms
78,352 KB
testcase_07 AC 357 ms
78,900 KB
testcase_08 AC 271 ms
78,168 KB
testcase_09 AC 239 ms
78,084 KB
testcase_10 AC 249 ms
78,556 KB
testcase_11 AC 244 ms
77,848 KB
testcase_12 AC 372 ms
78,072 KB
testcase_13 AC 366 ms
78,084 KB
testcase_14 AC 321 ms
78,432 KB
testcase_15 AC 336 ms
78,840 KB
testcase_16 AC 330 ms
78,324 KB
testcase_17 AC 297 ms
78,936 KB
testcase_18 AC 262 ms
78,212 KB
testcase_19 AC 274 ms
79,844 KB
testcase_20 AC 255 ms
79,088 KB
testcase_21 AC 242 ms
77,764 KB
testcase_22 AC 255 ms
78,212 KB
testcase_23 AC 240 ms
77,948 KB
testcase_24 AC 254 ms
79,244 KB
testcase_25 AC 251 ms
78,504 KB
testcase_26 AC 250 ms
77,924 KB
testcase_27 AC 193 ms
78,216 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 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]
            prod[j], v[j] = ext_gcd(g, u)
            g = g * prod[j] + u * v[j]
            prod[j] = safe_mod(prod[j], k)
            v[j] = 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
    x -= 1
    ans = 0
    for i in reversed(range(log)):
        if basis[i] == 0:
            continue
        u, v = msd[i], ans // powk[i]
        ans = op(ans, op_pow(basis[i], x // cnt[i] - v // u))
        x %= cnt[i]
    print(ans)
    return


def query3(x):
    x += 1
    ans, y = 0, 0
    for i in reversed(range(log)):
        if basis[i] == 0:
            u, v = x // powk[i] % k, y // powk[i] % k
            if u == v:
                continue
            if u > v:
                ans += cnt[i]
            break
        else:
            d, u = y // powk[i] % k, msd[i]
            y = op(y, op_pow(basis[i], -(d // u)))
            d %= u
            v = x // powk[i] % k - d
            ans += (v + u - 1) // u * cnt[i]
            if v % u > 0:
                break
            y = op(y, op_pow(basis[i], v // u))
    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)
0