这题其实真的很套路……
首先考虑一下 \(f(n)\) 的定义。
易得 \[f(n)=\begin{cases}
(-1)^{[n\ \text{is}\ \text{prime}]},&\forall_{d>1}\ d^2\not\mathop{|}n \\
0,&\exists_{d>1}\ d^2\mathop{|}n
\end{cases}\]
证明：
当 \(n\) 有平方因子时 \(f(n)\) 显然为 \(0\)。
否则考虑 \((-1)\) 的指数，即 \(\sum\limits_{i=0}^{\omega(n)} i\binom{\omega(n)}{i}\)，其中 \(\omega(n)\) 表示 \(n\) 的不同质因子个数。
由于 \(\binom{\omega(n)}i = \binom{\omega(n)}{\omega(n)-i}\)，故 \(\sum\limits_{i=0}^{\omega(n)} i\binom{\omega(n)}{i} = \frac 1 2\sum\limits_{i=0}^{\omega(n)} \omega(n)\binom{\omega(n)}{i} = 2^{\omega(n) - 1} \omega(n)\)。
仅当 \(\omega(n)=1\) 即 \(n\) 为质数时该式为 \(1\)，其余情况该式均为偶数。
证毕。
于是可以考虑算出无平方因子的数的个数，然后减去质数的贡献。
后者是一个经典问题，std 使用了 \(O(\frac{n^{3/4}}{\log n})\) 的 Min_25 筛解决，实际上还有诸如 Meissel-Lehmer 很多方法。
前者相当于求 \(\sum\limits_{i=1}^n \mu^2(i)\)。
考虑令 \(\text{msf}(n) = \max\limits_{d^2\mathop{|}n} d\) 即 \(n\) 的最大平方因子。
则 \[
\begin{align*}
\sum\limits_{i=1}^n \mu^2(i)
=&\sum\limits_{i=1}^n [\text{msf}(i)=1] \\
=&\sum\limits_{i=1}^n \sum\limits_{d|\text{msf}(i)} \mu(d) \\
=&\sum\limits_{d=1}^n \mu(d) \sum\limits_{d|\text{msf}(i)} 1
\end{align*}
\]
注意到 \(d\mathop{|}\text{msf}(i)\) 等价于 \(d^2\mathop{|}i\)，故 \[ \begin{align*} &\sum\limits_{d=1}^n \mu(d) \sum\limits_{d|\text{msf}(i)} 1 \\ =&\sum\limits_{d=1}^n \mu(d) \sum\limits_{d^2|i} 1 \\ =&\sum\limits_{d=1}^{\lfloor\sqrt n\rfloor} \mu(d)\left\lfloor\frac n{d^2}\right\rfloor \end{align*} \]
于是线性筛出 \(\left\lfloor\sqrt n\right\rfloor\) 以内的 \(\mu\) 值，此部分即可 \(O(\sqrt n)\) 求出。
（题外话：这个函数其实来自于 Elementary Number Theory and Its Applications 的某一道习题）
代码： 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
using namespace std;
const long long N = 1e10;
const int MX = 1e5;
const int mod = 998244353;
const int inv = 499122177;
long long n;
int lim;
int vis[MX + 5],prime[MX + 5],cnt,mu[MX + 5];
int tot,le[MX + 5],ge[MX + 5];
long long lis[2 * MX + 5];
int G[2 * MX + 5];
int ans;
inline int &id(long long x)
{
return x <= lim ? le[x] : ge[n / x];
}
int main()
{
mu[1] = 1;
for(register int i = 2;i <= MX;++i)
{
if(!vis[i])
mu[prime[++cnt] = i] = mod - 1;
for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
mu[i * prime[j]] = mod - mu[i];
}
}
scanf("%lld",&n),lim = sqrt(n);
for(register long long l = 1,r;l <= n;l = r + 1)
{
r = n / (n / l);
lis[id(n / l) = ++tot] = n / l;
G[tot] = (n / l % mod - 1 + mod) % mod;
}
for(register int k = 1;k <= cnt;++k)
{
int p = prime[k];
long long s = (long long)p * p;
for(register int i = 1;lis[i] >= s;++i)
G[i] = (G[i] - (G[id(lis[i] / p)] - (k - 1) + mod) % mod + mod) % mod;
}
for(register int i = 1;i <= lim;++i)
ans = (ans + (n / i / i) * mu[i] % mod) % mod;
ans = (ans - 2LL * G[1] % mod + mod) % mod;
printf("%d\n",ans);
}