結果

問題 No.1339 循環小数
コンテスト
ユーザー ntuda
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)
0