题目大意

有函数 $S(n)$ 定义如下：

$S(n)=\sum_{i=0}^{m-1} (-1)^i d_i^2=d_0^2-d_1^2+d_2^2-d_3^2+\cdots + (-1)^{m-1} d_{m-1}^2$

这里序列 ${di}$ 是正整数 $n \in [1,2\times 10^6]$ 的所有真约数（去重）的升序排列，求 $\sum{i=1}^n S(i)$

思路

我们先用样例 $n=6$ 打表看看有什么规律：

$n$	${(-1)^id_i^2}$	$S(n)$
$1$	$1^2$	$1$
$2$	$1^2\ , \ -2^2$	$-3$
$3$	$1^2\ , \ 3^2$	$-8$
$4$	$1^2\ , \ -2^2\ , \ 4^2$	$13$
$5$	$1^2\ , \ -5^2$	$-24$
$6$	$1^2\ , \ -2^2\ , \ 3^2\ , \ -6^2$	$-30$

我们发现，其求和可以变成，

$\begin{aligned} \sum_{i=1}^6 S(i)&= 1^2+(1^2-2^2)+(1^2-3^2)+(1^2-2^2+4^2)+(1^2-5^2)+(1^2-2^2+3^2-6^2)\\ &= 1^2\times 6 + (-2^2-2^2-2^2)+(-3^2+3^2)+4^2+(-5^2)+(-6^2)\\ \end{aligned}$

不难发现对于某个因子 $d$ 对于整体的贡献，就是其对于某个数 $x\in[1,n]$ 的升序排序的次序。例如因子 $2$ ，其整除的数有 ${2,4,6}$ 在这三个数的因子排序都是第2个，所以其贡献是 $-2^2\times 3$。

那么我们可以根据这个发现，先枚举 $[1,n]$ 的所有因子 $d$ ，然后枚举其倍数 ${d,2d,3d,\cdots | xd \le n}$ ，作一个计数器用于记录其出现的次数，然后根据其出现的次数作贡献即可。

即使用埃氏筛的思想，枚举倍数

这里还可以思考下是否存在 $O(n)$ 的线筛做法，我的思路是把每个数作质因数分解，看看是否存在递推（或者化归） $S(n)=S(p_1)S(p_2)\cdots S(p_k)$ 或者 $S(n)=aS(p_1)+bS(p_2)\cdots +cS(p_k)$ 的性质，然后就可以预处理质因数的 $S(n)$ 然后递推了。但是我代几个数发现似乎并不存在这样的性质，所以这里就不展开了。

代码

using ll = long long;

void sol()
{
	ll n; scanf("%lld",&n);
	ll s=n;  // 先把1的贡献记上
	int cnt[n+1];  //当然还可以使用bool省空间
	memset(cnt,0,sizeof(cnt));
	for(ll i=2; i<=n; i++)
	{
        ll t=i*i;
		s+=(cnt[i]&1? -t:t);
		cnt[i]++;
		for(ll j=2*i; j<=n; j+=i)
		{
			s+=(cnt[j]&1? -t:t);
			cnt[j]++;
		}
	}
	printf("%lld",s);
		
    return;
}

这里外循环 $n$ 次，然后内循环每个 $i$ 执行 $\lfloor \frac{n}{i} \rfloor$ 次，总的次数是，

$\begin{aligned} T(n)&=\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor\\ &=n\sum_{i=1}^n \frac{1}{i}\\ &\le n \int_{1}^{n} \frac{1}{x} dx =n\ln n \end{aligned}$

即时间复杂度是 $O(n\log n)$ 在2e6下还是可以过的