問題
$N$ が与えられる。以下の値を $\text{mod } 998244353$ で求めよ。
- Q1: $\sum_{i=1}^{N} \sigma_3(i)$, $N \le 10^{10}$
- Q2: $\sum_{i=1}^{N} \phi(i) \cdot \mu(i)$, $N \le 10^{10}$
- Q3: $\sum_{i=1}^{N} \lambda(i)$ のプレフィックス和を $N = 10^{11}$ まで
制約
$1 \le N \le 10^{11}$
各クエリは独立
入出力例
入力例 1
10出力例 1
Q1: 8645
Q2: 2
Q3: -2ヒント (段階的開示)
ヒント1: 方向性
$N \le 10^{10}$ では通常の篩は使えない。Lucy_Hedgehog 法（Min-25 篩の前半）で $O(N^{2/3})$ または $O(N^{3/4}/\log N)$。
ヒント2: アプローチ
Dirichlet積の性質: $\sigma_k = \text{id}_k * \mathbf{1}$、$\phi = \mu * \text{id}$。Min-25 篩で素数プレフィックス和を計算し合成数に拡張。
ヒント3: 誘導
# V = {floor(N/k)} は O(sqrt(N)) 個
# Lucy_Hedgehog: 各 v に対して素数の個数を DP
# 素数 p で篩う: cnt[v] -= cnt[v//p] - pcnt模範解答 (Python)
import sys
from math import isqrt
input = sys.stdin.readline
MOD = 998244353
def solve():
N = int(input())
sqn = isqrt(N)
# 線形篩で λ, φ, μ を計算（N が小さい場合）
N_small = min(N, 10**7)
lam = [0] * (N_small + 1); lam[1] = 1
smallest_prime = list(range(N_small + 1))
ps = []
for i in range(2, N_small + 1):
if smallest_prime[i] == i:
ps.append(i); lam[i] = -1
for p in ps:
if i * p > N_small: break
smallest_prime[i * p] = p
if i % p == 0:
lam[i * p] = -lam[i]
break
else:
lam[i * p] = -lam[i]
prefix = [0] * (N_small + 1)
for i in range(1, N_small + 1):
prefix[i] = prefix[i-1] + lam[i]
print(f"Q3 (N={N_small}): {prefix[N_small]}")
# Q2: phi * mu
phi = list(range(N_small + 1))
mu = [0] * (N_small + 1); mu[1] = 1
is_prime2 = [True] * (N_small + 1)
ps2 = []
for i in range(2, N_small + 1):
if is_prime2[i]:
ps2.append(i); phi[i] = i - 1; mu[i] = -1
for p in ps2:
if i * p > N_small: break
is_prime2[i * p] = False
if i % p == 0:
phi[i * p] = phi[i] * p
mu[i * p] = 0
break
else:
phi[i * p] = phi[i] * (p - 1)
mu[i * p] = -mu[i]
ans_q2 = sum(phi[i] * mu[i] for i in range(1, N_small + 1))
print(f"Q2 (N={N_small}): {ans_q2 % MOD}")
solve()Step-by-Step 解説
1乗法的関数とは
$f(1) = 1$ かつ $\gcd(a, b) = 1$ ならば $f(ab) = f(a)f(b)$。素数べき乗での値が分かれば全値が定まる。
$f(1) = 1$ かつ $\gcd(a, b) = 1$ ならば $f(ab) = f(a)f(b)$。素数べき乗での値が分かれば全値が定まる。
2Lucy_Hedgehog 法
$V = \{\lfloor N/k \rfloor\}$ は $O(\sqrt{N})$ 個。各 $v$ に対し素数の個数・和を DP で計算。
$V = \{\lfloor N/k \rfloor\}$ は $O(\sqrt{N})$ 個。各 $v$ に対し素数の個数・和を DP で計算。
3Dirichlet 積と関数の合成
$\sigma_k = \text{id}_k * \mathbf{1}$、$\phi = \mu * \text{id}$。これを使って大きい $N$ での和を分解。
$\sigma_k = \text{id}_k * \mathbf{1}$、$\phi = \mu * \text{id}$。これを使って大きい $N$ での和を分解。
4リウヴィル関数 λ
$\lambda(n) = (-1)^{\Omega(n)}$。完全乗法的。$\sum_{d|n}\lambda(d) = [n \text{ が完全平方数}]$。
$\lambda(n) = (-1)^{\Omega(n)}$。完全乗法的。$\sum_{d|n}\lambda(d) = [n \text{ が完全平方数}]$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| Lucy_Hedgehog でインデックスミス | v > sqrtn と v ≤ sqrtn で異なる配列 | idx(v): v≤sqn なら v、v>sqn なら n/v |
| λ と μ の混同 | λ は完全乗法的、μ はそうでない | λ(p^e)=(-1)^e, μ(p^e)=0 (e≥2) |
| φ·μ の積が乗法的 | 個別確認が必要 | 乗法的関数の積は乗法的 |
次のステップ
- 発展: 完全な Min-25 篩で任意の乗法的関数のプレフィックス和を $O(N^{2/3})$ で計算