問題
正整数 $N$ が与えられる。以下の3つの値を求めよ（mod $10^9+7$）。
- 問1: $\sum_{d=1}^{N} \phi(d)$（オイラーのトーシェント関数の総和）
- 問2: $\sum_{d=1}^{N} \mu(d)$（メビウス関数の総和）
- 問3: $\sum_{i=1}^{N} \sum_{j=1}^{N} \gcd(i, j)$
制約
$1 \leq N \leq 10^7$
入出力例
入力例 1
10出力例 1
32
-1
122$\sum \phi(d) = 1+1+2+2+4+2+6+4+6+4 = 32$、$\sum \mu(d) = -1$、$\sum_{i,j} \gcd(i,j)$ は変換公式で計算。
ヒント (段階的開示)
ヒント1: 方向性
線形篩（Linear Sieve）で $\mu$, $\phi$ を $O(N)$ で前計算。各合成数を最小素因数で1回だけ処理する。
ヒント2: アプローチ
$\mu$: $\mu(1)=1$, 素数 $p$ で $\mu(p)=-1$, $p^2 \mid n$ で $\mu(n)=0$, それ以外 $\mu(n)=-\mu(n/p)$。 $\phi$: $\phi(p)=p-1$, $p \mid n$ かつ $p^2 \nmid n$ なら $\phi(n)=\phi(n/p)(p-1)$, $p^2 \mid n$ なら $\phi(n)=\phi(n/p)\cdot p$。
ヒント3: GCD総和の変換
$\sum_{i,j} \gcd(i,j) = \sum_{d=1}^{N} \phi(d) \lfloor N/d \rfloor^2$（$\sum_{d \mid n} \phi(d) = n$ を利用）
模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
MOD = 10**9 + 7
N = int(input())
primes = []
min_prime = [0] * (N + 1)
mu = [0] * (N + 1)
phi = [0] * (N + 1)
mu[1] = phi[1] = 1
for i in range(2, N + 1):
if min_prime[i] == 0:
min_prime[i] = i
primes.append(i)
mu[i] = -1
phi[i] = i - 1
for p in primes:
if p > min_prime[i] or i * p > N:
break
min_prime[i * p] = p
if i % p == 0:
mu[i * p] = 0
phi[i * p] = phi[i] * p
else:
mu[i * p] = -mu[i]
phi[i * p] = phi[i] * (p - 1)
ans1 = sum(phi[1:N+1]) % MOD
ans2 = sum(mu[1:N+1])
ans3 = 0
for d in range(1, N + 1):
k = N // d
ans3 = (ans3 + phi[d] % MOD * (k % MOD) % MOD * (k % MOD)) % MOD
print(ans1)
print(ans2)
print(ans3)
solve()Step-by-Step 解説
1メビウス関数 $\mu$
$\mu(n) = 1$ ($n=1$), $(-1)^k$ ($k$個の異なる素数積), $0$ ($p^2 \mid n$)。重要性質: $\sum_{d \mid n} \mu(d) = [n=1]$。
$\mu(n) = 1$ ($n=1$), $(-1)^k$ ($k$個の異なる素数積), $0$ ($p^2 \mid n$)。重要性質: $\sum_{d \mid n} \mu(d) = [n=1]$。
2トーシェント関数 $\phi$
$\phi(n)$ = $n$ と互いに素な $\le n$ の正整数の個数。性質: $\sum_{d \mid n} \phi(d) = n$。
$\phi(n)$ = $n$ と互いに素な $\le n$ の正整数の個数。性質: $\sum_{d \mid n} \phi(d) = n$。
3線形篩
各合成数 $n = \mathrm{lpf}(n) \cdot (n / \mathrm{lpf}(n))$ の形で1回だけ生成。乗法的関数を $O(N)$ で計算。
各合成数 $n = \mathrm{lpf}(n) \cdot (n / \mathrm{lpf}(n))$ の形で1回だけ生成。乗法的関数を $O(N)$ で計算。
4GCD総和変換
$\sum_{i,j} \gcd(i,j) = \sum_d \phi(d) \cdot \#\{(i,j): d|i,d|j\} = \sum_d \phi(d) \lfloor N/d \rfloor^2$。
$\sum_{i,j} \gcd(i,j) = \sum_d \phi(d) \cdot \#\{(i,j): d|i,d|j\} = \sum_d \phi(d) \lfloor N/d \rfloor^2$。
5計算量
線形篩 $O(N)$、各クエリ $O(N)$。$N=10^7$ でも数秒以内。
線形篩 $O(N)$、各クエリ $O(N)$。$N=10^7$ でも数秒以内。
計算量
線形篩: $O(N)$ 時間・空間
問1,2: $O(N)$
問3: $O(N)$
合計: $O(N)$
問1,2: $O(N)$
問3: $O(N)$
合計: $O(N)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 線形篩の break 条件忘れ | ループ継続条件が不完全 | if p > min_prime[i] or i*p > N: break |
| mu の符号を mod する | mu は負になりうる | 問2は mod なしで出力 |
| phi の漸化式分岐ミス | $p \mid i$ と $p \nmid i$ で式を混同 | $p \mid i$: phi[i]*p、$p \nmid i$: phi[i]*(p-1) |
| floor を float で計算 | (N/d)**2 が float | (N//d)**2 で整数演算 |
次のステップ
- $\sum \mathrm{lcm}(i,j)$ の高速計算
- Min-25篩との組み合わせ
- $N \le 10^{11}$ の場合の $\sum \phi(d)$, $\sum \mu(d)$