結果

問題 No.3186 Big Order
コンテスト
ユーザー AngrySadEight
提出日時 2025-06-20 23:12:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 933 bytes
コンパイル時間 431 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 75,940 KB
最終ジャッジ日時 2025-06-20 23:12:55
合計ジャッジ時間 4,635 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1000001)

T = int(input())
for _ in range(T):
    def solve(A, B, C, ans):
        # print(A, B, C)
        # 何乗まで増やせば割り切れるか、二分探索
        if pow(A, B, C) != 0:
            return ans
        elif A % C == 0:
            times = 0
            A_cp = A
            while A_cp % C == 0:
                A_cp //= C
                times += 1
            ans += times * B
            return solve(A_cp, B, C, ans)
        else:
            ng = 0
            ok = B + 1
            while ok - ng > 1:
                mid = (ok + ng) // 2
                if pow(A, mid, C) == 0:
                    ok = mid
                else:
                    ng = mid
            ans += B // ok
            
            rem = pow(A, ok, C * C)
            return solve(rem // C, B // ok, C, ans)

    a, b, c = map(int, input().split())
    print(solve(a, b, c, 0) % 998244353)
0