1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
| 你这个题**关键突破点其实不是复杂度优化，而是一个模数上的“塌缩”**。
一旦看穿这一点，问题规模从「天文级」直接掉到「可算级」。
下面我按**纠错 → 关键化简 → 算法 → C++ 实现**来说明。
---
## 一、你当前思路里的一个根本性错误
你写的：
> 设 ( h(x) ) 为所有质因子 (-1) 的积
> 然后
> [
> \varphi(n^i) = \varphi(n)\cdot h^{i-1}(n)
> ]
这是**不对的**。
### 正确结论
若
[
n=\prod p_j^{e_j}
]
则
[
n^i=\prod p_j^{e_j i}
]
欧拉函数性质给出：
[
\boxed{
\varphi(n^i)=\varphi(n)\cdot n^{,i-1}
}
]
✅ **比值是 (n)**，不是你定义的 (h(n))。
---
## 二、真正的杀手结论（模 (n+1)）
我们重新看：
[
f(n)=\sum_{i=1}^{n} \varphi(n^i)\pmod{n+1}
]
代入正确公式：
[
\begin{aligned}
f(n)
&= \varphi(n)\sum_{i=1}^{n} n^{i-1} \pmod{n+1} \
&= \varphi(n)\sum_{j=0}^{n-1} n^j \pmod{n+1}
\end{aligned}
]
### 🔥 模 (n+1) 的核心简化
[
\boxed{
n \equiv -1 \pmod{n+1}
}
]
于是：
[
n^j \equiv (-1)^j
]
所以：
[
\sum_{j=0}^{n-1} n^j
\equiv \sum_{j=0}^{n-1} (-1)^j
==============================
\begin{cases}
0,& n\text{ 为偶数}\
1,& n\text{ 为奇数}
\end{cases}
]
### ⭐ 最终 f(n) 的闭式
[
\boxed{
f(n)=
\begin{cases}
0,& n\text{ 为偶数}\
\varphi(n),& n\text{ 为奇数}
\end{cases}
}
]
---
## 三、g(n) 的彻底化简
[
g(n)=\sum_{i=1}^{n} f(i)
]
代入上式：
[
\boxed{
g(n)=\sum_{\substack{1\le i\le n\ i\text{ 为奇}}} \varphi(i)
}
]
🎯 **问题变成：**
> 求不超过 (n) 的所有奇数的欧拉函数和
---
## 四、如何在 (n=5\times10^8) 下计算？
不能整表 sieve，但可以：
### 思路：分块 + 只筛奇数
* 只处理奇数：数量约 (n/2)
* 用 **分段筛** 计算区间内奇数的 (\varphi)
* 累加即可
* 内存只需一个块
复杂度：
* 时间：(O(n \log\log n))
* 内存：(O(\text{block size}))
---
## 五、C++ 实现（可直接跑）
|
