結果

問題 No.1339 循環小数
ユーザー aaaaaaaaaa2230
提出日時 2021-01-16 10:42:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 482 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 129,824 KB
最終ジャッジ日時 2024-11-27 10:41:01
合計ジャッジ時間 8,341 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

# X^K ≡ Y (mod M) となるような K を求める
def solve(X, Y, M):
    D = {}

    sq = int(M**.5)+1

    # Baby-step
    Z = 1
    for i in range(sq):
        Z = Z * X % M
        D[Z] = i+1

    if Y in D:
        return D[Y]

    # Giant-step
    R = pow(Z, M-2, M) # R = X^(-sq)

    for i in range(1, sq+1):
        Y = Y * R % M
        if Y in D:
            return D[Y] + i*sq
    return -1

t = int(input())
for _ in range(t):
    n = int(input())
    solve(10,1,n)
0