結果
問題 | No.1339 循環小数 |
ユーザー |
![]() |
提出日時 | 2023-12-01 12:05:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 155 ms / 2,000 ms |
コード長 | 812 bytes |
コンパイル時間 | 229 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 64,896 KB |
最終ジャッジ日時 | 2024-09-26 15:17:04 |
合計ジャッジ時間 | 4,927 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
import sysinput = sys.stdin.readlinedef div(n):i = 1SS = set()while i * i <= n:if n % i == 0:SS.add(i)SS.add(n//i)i += 1return SSdef euler_phi(n):temp = nval = nfor i in range(2, int(-(-n**0.5 // 1)) + 1):if temp % i == 0:val *= (i - 1)val //= iwhile temp % i == 0:temp //= iif temp != 1:val *= (temp - 1)val //= tempreturn valT = int(input())for _ in range(T):N = int(input())while N % 2 == 0:N //= 2while N % 5 == 0:N //= 5inf = 10 ** 18ans = inffor t in div(euler_phi(N)):if pow(10, t, N) == 1:ans = min(ans, t)print(ans) if ans != inf else print(1)