結果

問題 No.1339 循環小数
ユーザー convexineq
提出日時 2021-01-15 21:43:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 436 ms / 2,000 ms
コード長 686 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 81,708 KB
実行使用メモリ 129,728 KB
最終ジャッジ日時 2024-11-26 13:50:42
合計ジャッジ時間 6,695 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

def discrete_logarithm(a,b,MOD,permit0):
a %= MOD; b %= MOD
q = int(MOD**0.5)+2
# baby-step
h = 1 if MOD != 1 else 0
memo = {}
for i in range(q):
if h==b and (permit0 or i): return i
memo[h*b%MOD] = i
h = h*a%MOD
# giant-step # h = a^q
g = h
for i in range(q):
if g in memo:
res = (i+1)*q-memo[g]
if pow(a,res,MOD) == b: return res
else: return -1
g = g*h%MOD
return -1 #
T,*a = map(int,open(0).read().split())
for ai in a:
while ai%2==0: ai//=2
while ai%5==0: ai//=5
print(discrete_logarithm(10,1,ai,0))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0