問題
$T$ 個の整数 $N_i$（$N_i \le 10^{18}$）が与えられる。各 $N_i$ について：
- 素因数分解の結果（各素因数と指数）
- 最大素因数
- radical（相異なる素因数の積 = $\prod_{p | N} p$）
を出力せよ。
制約
| パラメータ | 範囲 |
|---|---|
| $T$ | $1 \le T \le 100$ |
| $N_i$ | $1 \le N_i \le 10^{18}$ |
入出力例
入力例 1
3
12
998244353
123456789012345678出力例 1
12: {2: 2, 3: 1} max=3 rad=6
998244353: {998244353: 1} max=998244353 rad=998244353
123456789012345678: {2: 1, 3: 2, 7: 1, ...} max=... rad=...$998244353$ は素数（NTT でよく使われるもの）。$12 = 2^2 \cdot 3$、radical = $2 \cdot 3 = 6$。
概念図: Miller-Rabin と Pollard's ρ のフロー
ヒント（段階的開示）
ヒント1: 方向性
$N \le 10^{18}$ の素因数分解は Miller-Rabin（確率的素数判定）+ Pollard's ρ（乱択因数分解）の組み合わせ。素数判定で素数なら終了、合成数なら ρ で因子を見つけて再帰。
ヒント2: アプローチ
- Miller-Rabin: 底 $\{2,3,...,37\}$ の12個で判定。$N \le 3.3 \times 10^{24}$ で確定的に正確
- Pollard's ρ: $f(x) = x^2 + c \bmod n$ でフロイドサイクル検出、$\gcd$ で因子抽出
- 再帰: 発見した因子 $d$ と $n/d$ を再帰的に素因数分解してマージ
ヒント3: コード骨格
def is_prime(n):
for a in [2,3,5,7,11,13,17,19,23,29,31,37]:
if n == a: return True
if n % a == 0: return False
if not miller_rabin(n, a): return False
return True
def factorize(n):
if n <= 1: return {}
if is_prime(n): return {n: 1}
d = pollard_rho(n)
f1 = factorize(d); f2 = factorize(n // d)
for k,v in f2.items(): f1[k] = f1.get(k,0) + v
return f1模範解答 (Python)
import sys
from math import gcd
from random import randint, seed
from collections import defaultdict
input = sys.stdin.readline
seed(42)
def miller_rabin(n, a):
if n % a == 0:
return n == a
d, r = n - 1, 0
while d % 2 == 0:
d //= 2; r += 1
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
for _ in range(r - 1):
x = x * x % n
if x == n - 1:
return True
return False
BASES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
def is_prime(n):
if n < 2: return False
for a in BASES:
if n == a: return True
if n % a == 0: return False
for a in BASES:
if not miller_rabin(n, a): return False
return True
def pollard_rho(n):
if n % 2 == 0: return 2
while True:
x = randint(2, n - 1)
y = x; c = randint(1, n - 1); d = 1
while d == 1:
x = (x * x + c) % n
y = (y * y + c) % n
y = (y * y + c) % n
d = gcd(abs(x - y), n)
if d != n: return d
def factorize(n):
if n <= 1: return defaultdict(int)
if is_prime(n):
res = defaultdict(int); res[n] += 1; return res
d = pollard_rho(n)
f1 = factorize(d); f2 = factorize(n // d)
for k, v in f2.items(): f1[k] += v
return f1
def main():
T = int(input())
for _ in range(T):
n = int(input())
if n == 1:
print("1: {} max=1 rad=1"); continue
factors = factorize(n)
sorted_f = sorted(factors.items())
max_p = max(factors.keys())
rad = 1
for p in factors: rad *= p
fstr = "{" + ", ".join(f"{p}: {e}" for p,e in sorted_f) + "}"
print(f"{n}: {fstr} max={max_p} rad={rad}")
main()Step-by-Step 解説
Step 1: Miller-Rabin 素数判定
$n-1 = 2^r \cdot d$ と分解し、$a^d \bmod n$ から強擬素数テストを実施。12個の底で $n \le 3.3 \times 10^{24}$ まで確定的に正確。計算量 $O(\log^2 n)$（各底ごと）。
Step 2: Pollard's ρ 因数分解
$f(x) = x^2 + c \bmod n$ の擬似乱数列でフロイドのサイクル検出。$\gcd(|x-y|, n) \ne 1, n$ で非自明因子を発見。$c$ を変えて再試行することで確率1で成功。期待計算量 $O(n^{1/4} \log n)$。
Step 3: 再帰的分解とマージ
発見した因子 $d$ と $n/d$ を再帰的に factorize し、辞書をマージ。最終的に素数の指数辞書が完成する。radical は相異なる素因数の積。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 底の比較を忘れる | n == a チェックなし | 各底 $a$ について if n == a: return True を先に |
| ρ が d==n に無限ループ | c の固定 | while True で c を再乱択 |
| $n=1$ の特殊処理なし | factorize(1) が空辞書 | if n <= 1: return {} |
次のステップ
- 発展問題: ECM（楕円曲線法）・General Number Field Sieve（現代の巨大数因数分解）
- 関連: RSA 暗号の安全性・素数生成・暗号プロトコルの実装