Day 041-Q5 — Miller-Rabin + Pollard's Rho（最大素因数・N≤10^18）

2026-05-24 赤色 Master / Phase 8+ ★★★★★★★★★ Miller-Rabin + Pollard's ρ + 最大素因数

問題

$Q$ 個の整数 $N_i$ ($N_i \le 10^{18}$) それぞれに対して、最大の素因数を出力せよ。$N_i = 1$ のときは 1 を出力する。

制約

$1 \le Q \le 100$
$1 \le N_i \le 10^{18}$
時間制限: 5sec / メモリ: 256MB

入出力例

入力例 1

3
12
998244353
1000000007000000049

出力例 1

3
998244353
1000000007

概念図: Pollard's ρ のサイクル検出

x₀ x₁ x₂ x₃ x₄ x₅ x₆ x₇ x₈ Floyd サイクル検出: x (亀): 1ステップ y (兎): 2ステップ gcd(|x-y|, N) > 1 → 非自明な因数発見！

ヒント（段階的開示）

ヒント1: 方向性
$N \le 10^{18}$ では試し割り法は不可（$10^9$ までしか試せない）。Miller-Rabin 確率的素数判定（決定的版）と Pollard's $\rho$ 法で素因数分解を $O(N^{1/4})$ で行う。
ヒント2: アプローチ
  1. Miller-Rabin: 基底 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} を使えば $N < 3.3 \times 10^{24}$ まで決定的に判定。
  2. Pollard's $\rho$: $f(x) = x^2 + c \pmod N$ のサイクル検出で非自明な因数を発見。
  3. 再帰的に素因数分解し最大素因数を返す。
ヒント3: 実装骨格 
from math import gcd

def miller_rabin(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    witnesses = [2,3,5,7,11,13,17,19,23,29,31,37]
    d, r = n - 1, 0
    while d % 2 == 0: d //= 2; r += 1
    for a in witnesses:
        if a >= n: continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1: continue
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1: break
        else: return False
    return True

def pollard_rho(n):
    if n % 2 == 0: return 2
    import random
    while True:
        x = random.randint(2, n-1)
        c = random.randint(1, n-1)
        y, d = x, 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

模範解答 (Python)

import sys
from math import gcd
import random
input = sys.stdin.readline

def miller_rabin(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for a in witnesses:
        if a >= n: continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1: continue
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1: break
        else:
            return False
    return True

def pollard_rho(n):
    if n % 2 == 0: return 2
    while True:
        x = random.randint(2, n - 1)
        c = random.randint(1, n - 1)
        y, d = x, 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 []
    if miller_rabin(n): return [n]
    for p in [2, 3, 5, 7, 11, 13]:
        if n % p == 0:
            res = []
            while n % p == 0:
                res.append(p)
                n //= p
            return res + factorize(n)
    d = pollard_rho(n)
    return factorize(d) + factorize(n // d)

def largest_prime_factor(n):
    if n == 1: return 1
    return max(factorize(n))

def solve():
    Q = int(input())
    for _ in range(Q):
        n = int(input())
        print(largest_prime_factor(n))

solve()

Step-by-Step 解説

1Miller-Rabin 素数判定
Fermat の小定理の拡張。$n-1 = 2^r \cdot d$ と書いて、$a^d \not\equiv 1$ かつ $a^{2^j d} \not\equiv -1$ ($j=0,...,r-1$) なら合成数の証人。特定の基底集合で $N < 3.3 \times 10^{24}$ まで確定的に判定可能。
2Pollard's ρ 法の原理
$f(x) = x^2 + c \pmod n$ の軌道はいずれサイクルを形成する（誕生日パラドックス的な衝突）。Floyd の2ポインタ法でサイクル中の2点 $x \neq y$ を見つけ、$\gcd(|x-y|, n) > 1$ となれば非自明な因数。
3再帰的素因数分解
factorize(n): 素数なら [n]、そうでなければ $\rho$ で因数 $d$ を見つけ factorize(d) + factorize(n/d)。
4小さい因数の前処理
2, 3, 5, ... などの小さな素数は試し割りで先に除いておくと $\rho$ の効率が上がる。
5最大素因数の抽出
全素因数を列挙して max を取る。$N \le 10^{18}$ なら素因数の個数は最大60程度（$2^{60} > 10^{18}$）。

計算量

Miller-Rabin（1回）: $O(\log^2 N)$（pow の高速計算含む）
Pollard's $\rho$（1回）: 期待 $O(N^{1/4} \log N)$
完全素因数分解: $O(N^{1/4} \log^2 N)$ 期待
$Q$ 個の入力: $O(Q \cdot N^{1/4} \log^2 N)$
$Q=100, N=10^{18}$: 約 $100 \times 10^{4.5} \approx 3 \times 10^6$ 演算（十分高速）

よくあるミス

ミス原因正しい書き方
Pollard's rho が無限ループc の選択が悪い場合 (d==n)if d != n: return d、さもなくば再試行
miller_rabin で a ≥ n を処理しない小さな n での境界if a ≥ n: continue
gcd の引数に負の値abs(x - y) を忘れるgcd(abs(x-y), n)
factorize(1) の基底ケース空リストを返す必要if n == 1: return []

次のステップ

  • 発展問題: $N \le 10^{18}$ の全素因数と指数を列挙（約数列挙に応用）
  • 応用: ECM（楕円曲線法）による大因数の分解（$10^{30}$ 超）
  • 類題: AtCoder ABC 176 E、競プロ典型90問 No.51

自己評価