問題
$T$ 個のテストケースが与えられる。各テストケースの $N$ に対して次の3つの総和を出力せよ（mod $10^9+7$）：
- $\displaystyle \sum_{i=1}^{N} \phi(i)$ — オイラーの φ 関数の総和
- $\displaystyle \sum_{i=1}^{N} |\mu(i)|$ — メビウス関数の絶対値の総和（平方因子を持たない整数の個数）
- $\displaystyle \sum_{i=1}^{N} \sigma(i)$ — 約数和関数の総和
制約
| パラメータ | 範囲 |
|---|---|
| $T$ | $1 \le T \le 10$ |
| $N$ | $1 \le N \le 10^7$ |
入出力例
入力例 1
2
10
100出力例 1
32 7 87
3044 61 8299N=10: φ総和=32（1+1+2+2+4+2+6+4+6+4）、|μ|=7（1,2,3,5,6,7,10のみ）、σ総和=87。
概念図: 線形篩の乗法的関数更新規則
ヒント（段階的開示）
ヒント1: 方向性
$\phi$、$\mu$、$\sigma$ はいずれも乗法的関数（$\gcd(m,n)=1$ なら $f(mn)=f(m)f(n)$）。線形篩で素数列挙と同時に $O(N)$ で全ての値を計算し、累積和でクエリに $O(1)$ 回答する。
ヒント2: アプローチ
| 条件 | φ(n) | μ(n) | σ(n) |
|---|---|---|---|
| n = 1 | 1 | 1 | 1 |
| n = p（素数） | p-1 | -1 | p+1 |
| p < lpf[n] (p∤n) | φ(n)×(p-1) | μ(n)×(-1) | σ(n)×(p+1) |
| p = lpf[n] (p|n) | φ(n)×p | 0 | σ(n/pe[n])×σ(pe[n]×p) |
ヒント3: コード骨格
phi = [0]*N; phi[1] = 1
mu = [0]*N; mu[1] = 1
sig = [0]*N; sig[1] = 1
lpf = [0]*N # lowest prime factor
pe = [0]*N # p^e where p^e || n
primes = []
for n in range(2, N):
if lpf[n] == 0: # n is prime
lpf[n] = pe[n] = n
phi[n] = n-1; mu[n] = -1; sig[n] = n+1
primes.append(n)
for p in primes:
if p > lpf[n] or n*p >= N: break
m = n*p; lpf[m] = p
if p < lpf[n]: # gcd(p,n)=1
pe[m] = p
phi[m] = phi[n]*(p-1)
mu[m] = -mu[n]
sig[m] = sig[n]*(p+1)
else: # p == lpf[n]
pe[m] = pe[n]*p
phi[m] = phi[n]*p
mu[m] = 0
sig[m] = sig[n//pe[n]] * (sig[pe[n]]*p+1)模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
def build(N):
phi = [0] * N
mu = [0] * N
sig = [0] * N
lpf = [0] * N
pe = [0] * N
phi[1] = mu[1] = sig[1] = 1
primes = []
for n in range(2, N):
if lpf[n] == 0:
lpf[n] = pe[n] = n
phi[n] = n - 1
mu[n] = -1
sig[n] = n + 1
primes.append(n)
for p in primes:
if p > lpf[n] or n * p >= N:
break
m = n * p
lpf[m] = p
if p < lpf[n]:
pe[m] = p
phi[m] = phi[n] * (p - 1)
mu[m] = -mu[n]
sig[m] = sig[n] * (p + 1)
else:
pe[m] = pe[n] * p
phi[m] = phi[n] * p
mu[m] = 0
# sigma(p^(e+1)) = sigma(p^e)*p + 1
sig_pe_new = sig[pe[n]] * p + 1
sig[m] = sig[n // pe[n]] * sig_pe_new
return phi, mu, sig
def main():
T = int(input())
Ns = [int(input()) for _ in range(T)]
maxN = max(Ns) + 1
phi, mu, sig = build(maxN)
phi_pre = [0] * maxN
mu_abs_pre = [0] * maxN
sig_pre = [0] * maxN
for i in range(1, maxN):
phi_pre[i] = (phi_pre[i-1] + phi[i]) % MOD
mu_abs_pre[i] = (mu_abs_pre[i-1] + (1 if mu[i] != 0 else 0)) % MOD
sig_pre[i] = (sig_pre[i-1] + sig[i]) % MOD
out = []
for N in Ns:
out.append(f"{phi_pre[N]} {mu_abs_pre[N]} {sig_pre[N]}")
print('\n'.join(out))
main()Step-by-Step 解説
Step 1: 線形篩の基本
各合成数 $n$ を「最小素因数 $p = \text{lpf}[n]$」によって一度だけ生成する。内側ループで $p > \text{lpf}[n]$ になったら break することで、各合成数が最小素因数でちょうど1回生成されることを保証する。
Step 2: pe 配列の役割
pe[n] は $n$ の最小素因数 $p$ の最大冪 $p^e$（$p^e \| n$）を保持する。これにより $n = p^e \times k$ と分解でき、$\sigma(n) = \sigma(k) \times \sigma(p^e)$ を使って更新できる。
Step 3: σ関数の特殊ケース
$\sigma(p^{e+1}) = \sigma(p^e) \times p + 1$（等比数列の和: $1 + p + \cdots + p^{e+1}$）。これを利用して sig[m] = sig[n//pe[n]] * (sig[pe[n]]*p + 1) で計算。
Step 4: 計算量
| 処理 | 計算量 |
|---|---|
| 線形篩全体 | $O(N)$ |
| 累積和構築 | $O(N)$ |
| 各クエリ | $O(1)$ |
| 全体（T クエリ） | $O(N + T)$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| pe の更新タイミング | p が lpf[n] と等しいケースを見落とす | pe[m] = pe[n] * p で更新 |
| σ の更新式が複雑 | sig(p^e * k) の分解を忘れる | sig[n//pe[n]] * (sig[pe[n]]*p+1) |
| |μ| の集計でμを直接使う | μ は -1, 0, 1 を取る | 1 if mu[i] != 0 else 0 |
| 配列サイズ不足 | n*p が N を超えるチェック漏れ | if n * p >= N: break を先に確認 |
次のステップ
発展問題: Dirichlet 畳み込み $\sum_{d|n} f(d)g(n/d)$ の高速計算（乗法的関数の積が乗法的）。メビウス反転公式の応用（GCD総和・LCM総和問題）。