Day 014-Q2 — 乗法的関数の高速列挙（Min-25 篩）

2026-04-27 赤色 Master / Phase 8+ ★★★★★★★★★ Euler φ の総和

問題

$N$ 以下の正整数 $k$ について Euler φ 関数の総和 $S(N) = \sum_{k=1}^{N} \varphi(k) \pmod{10^9+7}$ を求めよ。T 個のクエリ。

制約

$1 \le T \le 10$
$1 \le N_i \le 10^{11}$
時間制限: 3秒

入出力例

入力例 1

3
10
100
1000000000000

出力例 1

32
3044
（大きな値 mod 10^9+7）

ヒント (段階的開示)

ヒント1: 方向性
$N \le 10^{11}$ で単純な篩は不可能。Lucy_Hedgehog や Min-25 篩を使う。
ヒント2: アプローチ
Min-25 篩 2 段階: (1) 素数の prefix sum / (2) 合成数への乗法的拡張。
ヒント3: 誘導
φ は乗法的: $\varphi(p^k) = p^{k-1}(p-1)$。$\lfloor N/i \rfloor$ の形は $O(\sqrt{N})$ 種類しかない。

模範解答 (Python)

import sys
from math import isqrt

MOD = 10**9 + 7

def min25_sieve(N):
    if N <= 0:
        return 0
    sqN = isqrt(N)
    vs = []
    v = N
    while v > 0:
        vs.append(v)
        v = N // (N // v + 1)
    small = [0] * (sqN + 2)
    large = [0] * (sqN + 2)
    for v in vs:
        if v <= sqN:
            small[v] = v * (v - 1) // 2 % MOD
        else:
            i = N // v
            large[i] = v * (v - 1) // 2 % MOD
    primes = []
    for p in range(2, sqN + 1):
        if small[p] == small[p-1]:
            continue
        primes.append(p)
        p2 = p * p
        phi_p = (p - 1) % MOD
        for v in vs:
            if v < p2:
                break
            w = v // p
            fw = small[w] if w <= sqN else large[N // w]
            fp1 = small[p-1]
            if v <= sqN:
                small[v] = (small[v] - phi_p * (fw - fp1)) % MOD
            else:
                i = N // v
                large[i] = (large[i] - phi_p * (fw - fp1)) % MOD
    def S(v, j):
        if v <= 1:
            return 0
        fv = small[v] if v <= sqN else large[N // v]
        fp_prev = small[primes[j-1]-1] if j > 0 else 0
        result = (fv - fp_prev) % MOD
        for k in range(j, len(primes)):
            pk = primes[k]
            if pk * pk > v:
                break
            pe = pk
            phi_pe = pk - 1
            e = 1
            while pe * pk <= v:
                pe *= pk
                phi_pe *= pk
                e += 1
                result = (result + phi_pe * S(v // pe, k + 1)) % MOD
        return result
    return (S(N, 0) + 1) % MOD


def solve():
    T = int(input())
    for _ in range(T):
        N = int(input())
        print(min25_sieve(N))

solve()

Step-by-Step 解説

1Min-25 篩の有効性
$\lfloor N/i \rfloor$ のユニーク値は $O(\sqrt{N})$ 個のみ。
2第1フェーズ
全整数を素数とみなした $\varphi$ の和から、各素数で篩で除外。
3第2フェーズ
$\varphi$ の乗法性で素因数分解を通じて再帰分解。

よくあるミス

ミス原因正しい書き方
large/small 境界インデックス混同v ≤ sqN は small、それ以外は large
$\varphi(p^e)$ ミス$p^{e-1}(p-1)$
mod 忘れoverflow各計算後に %MOD

次のステップ

  • $\sum \mu(k) k^2$ の Min-25 篩拡張

自己評価

自分の回答

気づき・メモ