結果

問題 No.1648 Sum of Powers
ユーザー qwewe
提出日時 2025-05-14 12:51:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,933 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 130,120 KB
最終ジャッジ日時 2025-05-14 12:52:39
合計ジャッジ時間 12,996 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

MOD = 998244353

def baby_step_giant_step(a, b, mod):
    if a == 0:
        if b == 0:
            return 0
        else:
            return None
    if b == 1:
        return 0
    if mod == 1:
        return 0
    a %= mod
    b %= mod

    g = math.gcd(a, mod)
    if g != 1:
        if b % g != 0:
            return None
        a_div = a // g
        b_div = b // g
        mod_div = mod // g
        inv_a = pow(a_div, -1, mod_div)
        b_new = (b_div * inv_a) % mod_div
        res = baby_step_giant_step(a // g, b_new, mod_div)
        if res is None:
            return None
        return res + 1
    else:
        n = int(math.isqrt(mod)) + 1
        an = pow(a, n, mod)
        value = {}
        current = 1
        for i in range(n + 1):
            if current not in value:
                value[current] = i
            current = (current * a) % mod
        current = b
        for j in range(n + 1):
            if current in value:
                return j * n + value[current]
            current = (current * an) % mod
        return None

def main():
    A, B, P, Q = map(int, sys.stdin.readline().split())
    A = A % MOD
    B = B % MOD
    P = P % MOD
    Q = Q % MOD

    if (A == 2 % MOD) and ((1 - A + B) % MOD) == 0:
        if P == 2 and Q == 2:
            print(10**18)
            return

    if B == 0:
        if (A * Q) % MOD != P % MOD:
            print(-1)
            return
        else:
            if A == 0:
                if Q == 0 and P == 0:
                    print(10**18)
                    return
                else:
                    print(-1)
                    return
            else:
                m = baby_step_giant_step(A % MOD, Q % MOD, MOD)
                if m is None:
                    print(-1)
                    return
                else:
                    print(m + 1)
                    return

    inv_B = pow(B, MOD-2, MOD)

    forward = {}
    s0 = 2 % MOD
    s1 = A % MOD
    forward[(s1, s0)] = 1
    current_p, current_q = s1, s0
    found = False
    limit = 2 * 10**5
    for k in range(2, limit + 1):
        s_next = (A * current_q - B * current_p) % MOD
        current_p, current_q = s_next, current_p
        if (current_p, current_q) == (P, Q):
            print(k)
            return
        forward[(current_p, current_q)] = k

    current_p = P % MOD
    current_q = Q % MOD
    backward = {}
    backward[(current_p, current_q)] = 0
    for s in range(1, limit + 1):
        s_prev_prev = (A * current_q - current_p) * inv_B % MOD
        new_p = current_q
        new_q = s_prev_prev
        if (new_p, new_q) in forward:
            k = forward[(new_p, new_q)]
            print(k + s)
            return
        if (new_p, new_q) in backward:
            break
        backward[(new_p, new_q)] = s
        current_p, current_q = new_p, new_q

    print(-1)

if __name__ == "__main__":
    main()
0