```
占位。因为 shaber 洛谷一直提示我未按要求排版。
```
显然 $n$ 为奇数时 $f(n)=0$；下设 $n=2m$ 为偶数。我们有：
$$\begin{aligned}f(n)&=\sum_{k<n}(-1)^k\gcd(k,n)\\&=\sum_{k<n}(-1)^k\sum_{d|\gcd(k,n)}\varphi(d)\\&=\sum_{d|n}\varphi(d)\sum_{k<n~\&\&~d|k}(-1)^k\\&=\sum_{d|n~\&\&~2|d}\varphi(d)\left(\left\lfloor\frac nd\right\rfloor-1\right)-\sum_{d|n~\&\&~2\nmid d}\varphi(d)\end{aligned}$$
筛出 $\varphi$ 后，求 $f(n)$ 是容易的。
by XeCtera @ 2024-03-27 22:12:53
@[DoraYaoxy](/user/612567) 然后你可以 $O(n\ln n)$ 的时间处理多个 $f(n)$
by char_cha_ch @ 2024-03-27 22:13:40
@[XeCtera](/user/38785) 感谢。
by Kazeno_Akina @ 2024-03-27 22:14:14
@[DoraYaoxy](/user/612567) 比较悲伤的是我这个东西不是积性函数
by char_cha_ch @ 2024-03-27 22:16:10
@[char_cha_ch](/user/701221) 看懂了您的线性筛gcd思想，实在是感谢
by Hot_tear @ 2024-03-27 22:18:41
@[Hot_tear](/user/737112) 欸不是，我题看错了
by char_cha_ch @ 2024-03-27 22:19:06
@[char_cha_ch](/user/701221) 但是这个线性筛求gcd的思想还挺清奇的
by Hot_tear @ 2024-03-27 22:19:56
```
(续)
```
$$\begin{aligned}f(n)&=\sum_{d|n~\&\&~2|d}\varphi(d)\left(\frac nd-1\right)-\sum_{d|n~\&\&~2\nmid d}\varphi(d)\\
&\ge\varphi(2)\left(\dfrac n2-1\right)-\sum_{d|m}\varphi(d)\\
&=m-1-m\\
&=-1\end{aligned}$$
取等当且仅当 $m=1$ 或 $m$ 为质数。
这就证明了 $f(n)_{\min}=-1$。
by XeCtera @ 2024-03-27 22:24:06
@[DoraYaoxy](/user/612567)
by XeCtera @ 2024-03-27 22:24:56
@[XeCtera](/user/38785) 谢谢您qwq。所以这样是不是就可以在 $O(n \sqrt n)$ 内求解 $f(n)$ 的前缀和了？
by Kazeno_Akina @ 2024-03-27 22:31:11