题意
设 $f(n)$ 为 $n=ab$ 的方案数，其中 $a,b$ 为无平方因子数。求 $displaystyle sum_{i=1}^nf(i)$，$n leq 2e7$。
分析
显然，可发现 $f = mu ^2 * mu ^2$.
即 $displaystyle f(n) = sum_{d | n} mu^2(d) mu^2(frac{n}{d})$
那么可以这样化简目标式
$$egin{aligned} & sum_{i = 1}^{n} f(i) \ =& sum_{i = 1}^{n} sum_{d | i} mu^2 (d) mu^2 (frac{i}{d}) \ =& sum_{d = 1}^{n} sum_{d | i}^{1leq i leq n} mu^2(d) mu^2(frac{i}{d}) \ = & sum_{d = 1}^{n} mu^2 (d) sum_{i = 1}^{lfloor frac{n}{d} floor} mu^2 (i) end{aligned}$$
那么重点在于预处理出 $mu^2$ 的前缀和，然后整除分块一下就可以了。
这里预处理的复杂度为 $O(n)$（可以用这一结论 $displaystyle sum_{i=1}^n mu (i)^2 = sum_{i=1}^{left lfloor sqrt n ight floor}mu (i)left lfloor frac{n}{i^2} ight floor$ 降至 $O(sqrt n)$），单次询问的复杂度为 $O(sqrt n)$
数组全用 long long 会MLE。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e7 + 10; int p[maxn], flg[maxn], mu[maxn]; ll sum_mu[maxn]; int n; void init(int N) { int tot = 0; mu[1] = 1; for (int i = 2; i <= N; ++i) { if (!flg[i]) { p[++tot] = i; mu[i] = -1; } for (int j = 1; j <= tot && i * p[j] <= N; ++j) { flg[i * p[j]] = 1; if (i % p[j] == 0) { mu[i * p[j]] = 0; break; } mu[i * p[j]] = -mu[i]; } } for (int i = 1; i <= N; ++i)sum_mu[i] = sum_mu[i-1] + mu[i]*mu[i]; } int main() { init(2e7); int T; scanf("%d", &T); while(T--) { scanf("%d", &n); ll ans = 0; for(int l=1, r;l <= n;l = r+1) { r = n / (n/l); ans += sum_mu[n/l] * (sum_mu[r] - sum_mu[l-1]); } printf("%lld ", ans); } return 0; }
参考链接：
1. http://www.cfzhao.com/2019/05/23/%E8%AE%A1%E8%92%9C%E5%AE%A2-a1956-sum/