結果
問題 | No.1339 循環小数 |
ユーザー | persimmon-persimmon |
提出日時 | 2021-02-12 13:55:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 473 ms / 2,000 ms |
コード長 | 935 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 87,284 KB |
実行使用メモリ | 129,980 KB |
最終ジャッジ日時 | 2023-09-26 13:06:21 |
合計ジャッジ時間 | 8,639 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
71,412 KB |
testcase_01 | AC | 84 ms
75,912 KB |
testcase_02 | AC | 77 ms
76,200 KB |
testcase_03 | AC | 77 ms
75,924 KB |
testcase_04 | AC | 76 ms
76,072 KB |
testcase_05 | AC | 76 ms
76,108 KB |
testcase_06 | AC | 76 ms
75,760 KB |
testcase_07 | AC | 86 ms
76,508 KB |
testcase_08 | AC | 75 ms
76,032 KB |
testcase_09 | AC | 74 ms
75,928 KB |
testcase_10 | AC | 77 ms
75,928 KB |
testcase_11 | AC | 79 ms
76,332 KB |
testcase_12 | AC | 79 ms
76,292 KB |
testcase_13 | AC | 78 ms
76,160 KB |
testcase_14 | AC | 79 ms
76,276 KB |
testcase_15 | AC | 78 ms
76,084 KB |
testcase_16 | AC | 78 ms
76,372 KB |
testcase_17 | AC | 76 ms
76,088 KB |
testcase_18 | AC | 76 ms
76,336 KB |
testcase_19 | AC | 80 ms
76,140 KB |
testcase_20 | AC | 79 ms
76,248 KB |
testcase_21 | AC | 282 ms
109,024 KB |
testcase_22 | AC | 315 ms
120,908 KB |
testcase_23 | AC | 302 ms
113,452 KB |
testcase_24 | AC | 287 ms
112,572 KB |
testcase_25 | AC | 306 ms
114,240 KB |
testcase_26 | AC | 303 ms
112,748 KB |
testcase_27 | AC | 299 ms
115,872 KB |
testcase_28 | AC | 304 ms
116,216 KB |
testcase_29 | AC | 265 ms
112,820 KB |
testcase_30 | AC | 281 ms
112,200 KB |
testcase_31 | AC | 408 ms
129,668 KB |
testcase_32 | AC | 418 ms
129,432 KB |
testcase_33 | AC | 300 ms
113,628 KB |
testcase_34 | AC | 219 ms
102,584 KB |
testcase_35 | AC | 473 ms
129,980 KB |
testcase_36 | AC | 292 ms
112,784 KB |
ソースコード
# baby-step-giant-step # 離散対数問題(Discrete Logarithm Problem)を解くアルゴリズム。 # あるX,Y,M について X^K≡Y (mod M) となる K を求める。 # X,Mは互いに素 def bsgs(x,y,m): c=int(m**0.5)+1 d={} # baby-step now=1 for i in range(c): d[now]=i now*=x now%=m if now==y:return i+1 # giant-step gs=now now=1 for i in range(c): now*=gs now%=n if now in d:return (i+1)*c-d[now] return n # now=1からはじめ、以下を繰り返す。 # ・now%=n # ・now*=10 # 過去に一度出たnowが再び出たらそこから循環する。nowの取りうる値は0~n-1なので循環は高々n個から成る。 # 10**k=1 (mod n)となるkで循環する # baby-step-giant-step if __name__=='__main__': t=int(input()) cases=[int(input()) for _ in range(t)] for n in cases: while n%5==0:n//=5 while n%2==0:n//=2 retb=bsgs(10,1,n) print(retb)