素因数分解と累乗剰余による O(√p + k·d·log p) 実装
原始根（Primitive Root）とは、素数 p に対して、g の累乗 g1, g2, ..., gp-1 を p で割った余りが、すべて異なる値になるような整数 g のことです。
例えば p = 7 の場合、g = 3 は以下のように原始根になります：
これらはすべて異なる値（1, 2, 3, 4, 5, 6）になるため、3 は 7 の原始根です。
73 27 の原始根は 3 と 5 の2つあり、最小は 3 です。
原始根を効率的に判定するために、数学的な性質を活用します：
#!/bin/python3
import math
import os
import random
import re
import sys
from typing import List
def prime_factors(n: int) -> List[int]:
"""
nの素因数をリストで返す（重複なし）
Time Complexity: O(√n)
"""
factors = []
# 2で割り切れる場合
if n % 2 == 0:
factors.append(2)
while n % 2 == 0:
n //= 2
# 3以降の奇数でチェック
i = 3
while i * i <= n:
if n % i == 0:
factors.append(i)
while n % i == 0:
n //= i
i += 2
# nが1より大きければ、それ自体が素数
if n > 1:
factors.append(n)
return factors
def is_primitive_root(g: int, p: int, prime_divisors: List[int]) -> bool:
"""
gがpの原始根かどうかを判定
Args:
g: 判定対象の整数
p: 素数
prime_divisors: (p-1)の素因数リスト
Returns:
gが原始根ならTrue
Time Complexity: O(d·log p) where d = len(prime_divisors)
"""
phi = p - 1
# 各素因数qについて、g^((p-1)/q) ≢ 1 (mod p) を確認
for q in prime_divisors:
if pow(g, phi // q, p) == 1:
return False
return True
def euler_phi(n: int) -> int:
"""
オイラーのトーシェント関数 φ(n) を計算
Time Complexity: O(√n)
"""
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
if n > 1:
result -= result // n
return result
def solve_competitive(p: int) -> tuple:
"""
競技プログラミング向け実装
Args:
p: 素数
Returns:
(最小原始根, 原始根の総数)
Time Complexity: O(√p + k·d·log p)
where k = 最小原始根の値, d = (p-1)の素因数の個数
Space Complexity: O(d)
"""
# (p-1)の素因数を求める
prime_divisors = prime_factors(p - 1)
# 最小原始根を探索
smallest_root = 0
for g in range(2, p):
if is_primitive_root(g, p, prime_divisors):
smallest_root = g
break
# 原始根の総数 = φ(p-1)
total_count = euler_phi(p - 1)
return smallest_root, total_count
if __name__ == '__main__':
p = int(input().strip())
smallest, total = solve_competitive(p)
print(f"{smallest} {total}")
📋 ステップバイステップの流れ：
💡 初学者向けポイント：
• ループAは候補 g を順番にチェックする外側のループ
• ループBは各素因数 q で判定する内側のループ
• ループバックの矢印は g++ 後に判定ステップに戻ることを示す
• ステップ番号で処理の順序が一目でわかる
| 項目 | 本実装 | 全探索（素朴） | 備考 |
|---|---|---|---|
| 時間計算量 |
O(√p + k·d·log p)
|
O(p²·log p)
|
k = 最小原始根（通常小さい） d = (p-1)の素因数個数 |
| 空間計算量 |
O(d)
|
O(p)
|
素因数リストのみ保存 |
| 実装コスト | 中 | 低 | 素因数分解が必要 |
| p=10⁹での実用性 | ◎ 高速 | × TLE | 制約の上限で性能差が顕著 |