公式渲染压力测试

P8670 [蓝桥杯 2018 国 B] 矩阵求和 题解

前置芝士 / 题目

• \(\gcd\) 的性质
• 欧拉函数 \(\varphi\) 及其性质

前置题目：P2398 GCD SUM。

思路

简要题意：求

$$ \sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i,j)^2 $$

首先枚举暴力，肯定 T 飞，期望得分 30pts。

// #include <algorithm>
for (reg int i = 1; i <= n; ++i)
    ans = (ans + (i * i) % mod) % mod;
for (reg int i = 2; i <= n; ++i)
    for (reg int j = 1; j <= i - 1; ++j)
        ans += 2 * __gcd(i, j) * __gcd(i, j);

不会用莫比乌斯反演，乱搞一下。
类似的带 \(\gcd\) 的结论：

$$ \begin{aligned} \sum_{i=1}^{n} \sum_{j=1}^{n} f\left(\gcd(i,j)\right) &=\sum_{d=1}^{n} d \sum_{i=1}^{n} \sum_{j=1}^{n} [f \left( \gcd(i, j) \right)=d] \\ &=\sum_{d=1}^{n} f\left(d\right) \sum_{i=1}^{n} \sum_{j=1}^{n} [\gcd(i, j)=d] \\ &=\sum_{d=1}^{n} f\left(d\right) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} [\gcd(i, j)=1] \end{aligned} $$

\([\gcd(i,j)=1]\) 不就是两者互质么，那么来个欧拉函数解决问题。

参考 P2158 [SDOI2008] 仪仗队，排除掉重复计算。

$$ \begin{aligned} \sum_{d=1}^{n} f\left(d\right) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} [\gcd(i, j)=1] &=\sum_{d=1}^{n} f\left(d\right) \left( 2 \times \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \varphi\left(n\right)-1 \right) \end{aligned} $$

有了这个结论就可以愉快的刷多倍经验了。

贴个代码

inline void Euler(i64 n)
{
	phi[1] = 1;
    for (reg int i = 2; i <= n; ++i)
    {
        if (!prime[i]) prime[++prime[0]] = i, phi[i] = i - 1;
        for (reg int j = 1; j <= prime[0] && i * prime[j] <= n; ++j)
        {
            prime[i * prime[j]] = 1;
            if (!(i % prime[j])) { 
            	 phi[i * prime[j]] = phi[i] * prime[j]; break; }
            else phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for (reg int i = 1; i <= n; ++i)
    	phisum[i] = phisum[i - 1] + phi[i];
}

int main()
{
	Euler(n);
	for (reg i64 i = 1; i <= n; ++i)
	    ans = (ans + ((i * i) % mod) * ((phisum[n / i] * 2 - 1) % mod) % mod) % mod;
}