問題
以下の3つを解け。
- A: $\sum_{i=1}^{N} \phi(i)$
- B: $\sum_{i=1}^{N} \sum_{j=1}^{N} \gcd(i, j)$
- C: $\text{lcm}(1, 2, \ldots, N) \bmod 10^9+7$
制約
$1 \le N \le 2 \times 10^5$
入出力例
入力例 1
10出力例 1
A: 32
B: 330
C: 232792560ヒント (段階的開示)
ヒント1: 方向性
A: 線形篩で $\phi(i)$ を $O(N)$ 全計算。B: $\sum_{d|N}\phi(d)=N$ とメビウス反転。C: lcm = 各素数 $p^k \le N$ の最大冪の積。
ヒント2: アプローチ
B: $\sum_{i,j}\gcd(i,j) = \sum_d \phi(d) \lfloor N/d \rfloor^2$。C: エラトステネスで素数を取得し $p^k \le N$ の最大冪の積。
ヒント3: 誘導
def linear_sieve(n):
phi = list(range(n+1))
primes = []
for i in range(2, n+1):
if phi[i] == i:
primes.append(i); phi[i] = i - 1
for p in primes:
if i * p > n: break
if i % p == 0:
phi[i * p] = phi[i] * p; break
else:
phi[i * p] = phi[i] * (p - 1)
return phi, primes模範解答 (Python)
import sys
input = sys.stdin.readline
def main():
N = int(input())
MOD = 10**9 + 7
phi = list(range(N + 1))
primes = []
is_composite = [False] * (N + 1)
for i in range(2, N + 1):
if not is_composite[i]:
primes.append(i); phi[i] = i - 1
for p in primes:
if i * p > N: break
is_composite[i * p] = True
if i % p == 0:
phi[i * p] = phi[i] * p; break
else:
phi[i * p] = phi[i] * (p - 1)
ans_A = sum(phi[1:N+1])
ans_B = sum(phi[d] * (N // d) ** 2 for d in range(1, N + 1))
ans_C = 1
for p in primes:
pk = p
while pk <= N:
pk *= p
pk //= p
ans_C = ans_C * pk % MOD
print(f"A: {ans_A}")
print(f"B: {ans_B}")
print(f"C: {ans_C}")
main()Step-by-Step 解説
1Linear Sieve
各合成数は「最小素因子 × 何か」の形で一度だけ生成。$\phi$ 更新は $i \% p \neq 0$ なら $\phi(ip) = \phi(i)(p-1)$、そうでなければ $p \cdot \phi(i)$。
各合成数は「最小素因子 × 何か」の形で一度だけ生成。$\phi$ 更新は $i \% p \neq 0$ なら $\phi(ip) = \phi(i)(p-1)$、そうでなければ $p \cdot \phi(i)$。
2問題B
$\sum_{i,j}\gcd(i,j) = \sum_d d \cdot \#\{(i,j):\gcd=d\}$。メビウス反転と $\sum_{d|n}\phi(d)=n$ で $\sum_d \phi(d)\lfloor N/d\rfloor^2$。
$\sum_{i,j}\gcd(i,j) = \sum_d d \cdot \#\{(i,j):\gcd=d\}$。メビウス反転と $\sum_{d|n}\phi(d)=n$ で $\sum_d \phi(d)\lfloor N/d\rfloor^2$。
3問題C — lcm の構造
$\text{lcm}(1,...,N) = \prod_{p \text{ prime}, p \le N} p^{\lfloor \log_p N \rfloor}$。
$\text{lcm}(1,...,N) = \prod_{p \text{ prime}, p \le N} p^{\lfloor \log_p N \rfloor}$。
4gcd 公式の証明
$\gcd(a^m-1, a^n-1) = a^{\gcd(m,n)}-1$ をユークリッド互除法の類似で。
$\gcd(a^m-1, a^n-1) = a^{\gcd(m,n)}-1$ をユークリッド互除法の類似で。
5計算量
線形篩 $O(N)$、A/B $O(N)$、C $O(\pi(N))$。
線形篩 $O(N)$、A/B $O(N)$、C $O(\pi(N))$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
線形篩で phi[1] = 1 を忘れる | 初期値漏れ | phi = list(range(N+1)) で解決 |
問題Bで d * floor(N/d)^2 と誤る | 公式の誤解 | 正しくは phi(d) * floor(N/d)^2 |
| 問題Cでオーバーフロー | 大きな積 | 各ステップで % MOD する |
次のステップ
- 発展: $\sum_{i,j}\phi(\gcd(i,j))$ を $O(N\sqrt{N})$ で
- メビウス関数 $\mu$ と反転公式の応用