题解：P10321 奉献（Dedication）

· · 题解

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

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 题的位置了。