自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:56:54，当前版本为作者最后更新于2024-04-05 22:38:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先按照题意模拟，我们可以得到这样一段代码：

double ans = 0;
for(int a=1;a<=n;++a){
    int len = d(a);
    for(int b=1;b<=a;++b){
        if(vis[a][b]) continue;
        ans += len*log2(len);
        for(int i=1;a*i<=n;++i){
            if(vis[a*i][b*i]) continue;
            vis[a*i][b*i] = true;
            ans += d(i);
        }
     }
}

经过一些测试可以发现，最内层循环中判断 $(ai,bi)$ 是否被填写过其实是不必要的，即这个位置一定没被填写。

为什么呢？我们可以先证明找到的 $b$ 都满足 $\gcd(a,b)=1$ —— 因为如果 $\gcd(a,b)=d$ 且 $d>1$，则在此之前一定找到过 $(a/d,b/d)$ 位置，然后将其整数倍位置上都填了数（这其中也包括 $(a,b)$ 位置）。对于 $\gcd(a,b)=1$ 的位置，不能从一个较小的位置算出它，这就证明了结论。

现在答案就可以写为：

$$\sum_{a=1}^n \sum_{b=1}^a[\gcd(a,b)=1]\left( d_a\log_2 d_a+\sum_{i=1}^{\lfloor n/a \rfloor} d_i\right) $$

可以发现括号里那一大块是和 $b$ 无关的，可以直接记为 $f(a)$。只要求出 $d_i$，$f(a)$ 就可以直接用前缀和来计算。根据简单的递推公式 $d_i=1+d_{\lfloor i/10 \rfloor}$ 就能以 $\Theta(n)$ 的时间复杂度处理。

现在答案是

$$\sum_{a=1}^n f(a) \sum_{b=1}^a [\gcd(a,b)=1]$$

现在的问题就是要求出 $a$ 以内与其互质的正整数个数，这个就是欧拉函数 $\varphi(a)$。如果不了解相关知识，也可以在 OEIS 上搜索来得到结论。因为它是积性函数，可以使用线性筛的方法求出 $n$ 以内的所有函数值。

总时间复杂度为 $\Theta(n)$。当然也可以使用一些积性函数求和的方法做到更快，但那样这题就不能放在 B 题的位置了。