結果
問題 |
No.1339 循環小数
|
ユーザー |
![]() |
提出日時 | 2025-08-16 19:12:40 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,742 bytes |
コンパイル時間 | 287 ms |
コンパイル使用メモリ | 82,736 KB |
実行使用メモリ | 78,720 KB |
最終ジャッジ日時 | 2025-08-16 19:12:45 |
合計ジャッジ時間 | 4,897 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 WA * 35 |
ソースコード
from math import lcm from collections import deque def PrimeList(N): P = [1] * (N + 1) P[0] = P[1] = 0 for i in range(2, N + 1): if P[i]: for j in range(i + i, N + 1, i): P[j] = 0 PL = [] for i in range(N + 1): if P[i] == 1: PL.append(i) return PL maxn = 10 ** 9 PL = PrimeList(int(maxn**0.5) + 1) PL = set(PL) from collections import defaultdict def factorization(x): dic = defaultdict(int) for p in PL: if x in PL: dic[x] = 1 return dic while x % p == 0: dic[p] += 1 x //= p if x == 1: return dic dic[x] = 1 return dic # 約数の数 def N_divisors(x): dic = factorization(x) ret = 1 for v in dic.values(): ret *= (v+1) return ret # 素因数の数 def n_factorization(x): cnt = 0 for p in PL: if x in PL: cnt += 1 return cnt while x % p == 0: cnt += 1 x //= p if x == 1: return cnt # ここには来ないはず print("factorization error") return "error" def divisors(PF): D = deque([1]) for k, v in PF.items(): D2 = deque() while D: x = D.pop() for i in range(v + 1): D2.append(x * pow(k, i)) D = D2 return sorted(list(D)) for _ in range(int(input())): N = int(input()) dic = factorization(N) ans = 1 for k in dic.keys(): if k in [2,3,5]: continue D = divisors(factorization(k-1)) for d in D: if pow(10,d,N) == 1: break ans = lcm(ans,d) print(ans)