結果

問題 No.1648 Sum of Powers
ユーザー gew1fw
提出日時 2025-06-12 14:31:13
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,507 bytes
コンパイル時間 442 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 585,332 KB
最終ジャッジ日時 2025-06-12 14:31:32
合計ジャッジ時間 5,752 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 MLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

MOD = 998244353

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

    if B_mod == 0:
        if (A_mod * Q_mod) % MOD != P_mod:
            print(10**18)
            return

        if A_mod == 0:
            print(10**18)
            return

        target = P_mod
        a = A_mod
        if a == 1:
            print(10**18)
            return

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

            n = int(mod ** 0.5) + 1
            table = dict()
            current = 1
            for j in range(n):
                if current not in table:
                    table[current] = j
                current = (current * a) % mod

            a_n = pow(a, n, mod)
            a_n_inv = pow(a_n, mod - 2, mod)
            current = b
            for i in range(n):
                if current in table:
                    return i * n + table[current]
                current = (current * a_n_inv) % mod
            return -1

        x = baby_step_giant_step(a, target, MOD)
        if x == -1:
            print(10**18)
            return

        if x >= 2:
            print(x)
        else:
            print(10**18)
    else:
        inv_B = pow(B_mod, MOD-2, MOD)
        current_S = P_mod
        prev_S = Q_mod
        steps = 0
        visited = set()

        while True:
            if (current_S, prev_S) == (A_mod, 2):
                if steps == 0:
                    next_prev_S = (A_mod * prev_S - current_S) * inv_B % MOD
                    if prev_S == next_prev_S and current_S == prev_S:
                        print(10**18)
                        return
                    else:
                        print(10**18)
                        return
                else:
                    print(steps + 1)
                    return

            if (current_S, prev_S) in visited:
                if (A_mod, 2) in visited:
                    print(10**18)
                    return
                else:
                    print(10**18)
                    return

            visited.add( (current_S, prev_S) )
            next_prev_S = (A_mod * prev_S - current_S) * inv_B % MOD
            current_S, prev_S = prev_S, next_prev_S
            steps += 1

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