結果

問題 No.3264 岩井数
コンテスト
ユーザー urunea
提出日時 2025-09-06 14:56:15
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,658 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 67,844 KB
最終ジャッジ日時 2025-09-06 14:56:23
合計ジャッジ時間 4,483 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import sys

def prime_factors(n):
    pf = {}
    x = n
    d = 2
    while d * d <= x:
        while x % d == 0:
            pf[d] = pf.get(d, 0) + 1
            x //= d
        d += 1 if d == 2 else 2  
    if x > 1:
        pf[x] = pf.get(x, 0) + 1
    return pf

def totient(n, pf):
    res = n
    for p in pf:
        res = res // p * (p - 1)
    return res

def divisors_from_pf(pf):
    # pf: {prime:exp}
    divs = [1]
    for p, e in pf.items():
        cur = []
        powp = 1
        for _ in range(e+1):
            for d in divs:
                cur.append(d * powp)
            powp *= p
        divs = cur
    return divs

N = int(sys.stdin.readline().strip())
# factorize N
pfN = prime_factors(N)
phi = totient(N, pfN)

# factorize phi to enumerate its divisors (we need sorted divisors)
pf_phi = prime_factors(phi)
divs = divisors_from_pf(pf_phi)
divs.sort()

# find multiplicative order k of 10 mod N (smallest d | phi with 10^d = 1 mod N)
k = None
for d in divs:
    if pow(10, d, N) == 1:
        k = d
        break

if k is None:
    # 理論上あり得ないはず（gcd(10,N)=1 なら位数は存在する）
    raise RuntimeError("order not found")

# choose t so that L = t*k >= 9, and L <= 2000 (we can choose minimal t)
t = (9 + k - 1) // k
L = t * k
# safety check: problem guarantees a solution exists within bounds,
# but let's assert L <= 2000
if L > 2000:
    # 理論上このケースは問題文の条件下で起きないはずですが念のため
    raise RuntimeError("cannot make length within [9,2000]")

# 出力: L 個の '9'（これは 10^L - 1 で N の倍数かつ Iwai 数）
print('9' * L)
0