Hellc

【题目描述】

给定 $n$，求：

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

$1 \leq n \leq 2^{32}$

【题目链接】

BZOJ 2705 Longge的问题 【SDOI 2010】

【解题思路】

$$ \begin{align*} \sum_{i = 1}^n \gcd(i, n) &= \sum_{d \mid n} \sum_{i = 1}^n d[\gcd(i, n) = d] \\ &= \sum_{d \mid n} d \sum_{i = 1}^n[\gcd(i, n) = d] \\ &= \sum_{d \mid n} d \sum_{i = 1}^{\left \lfloor \frac n d \right \rfloor}[\gcd(i, \frac n d) = 1] \\ &=\sum_{d \mid n} d \varphi(\frac n d) \end{align*} $$

因为只有一组询问，所以我们可以枚举 $n$ 的约数，然后暴力计算 $\varphi(\frac n d)$ 即可，这样是可以过的。

但在这里我们讨论一下 $f(n) = \sum_{d \mid n}d\ \varphi(\frac n d)$ ，即 $f = \varphi \times \tau$ 的筛法。

积性函数的狄利克雷卷积还是积性函数，所以我们考虑 $f(p^a)$ 即可。

$$ \begin{align*} f(p^a) &= \sum_{i = 0}^a p^i \ \varphi(p^{a - i}) \\ &= p^a + \sum_{i = 0}^{a - 1} p^i \ \varphi(p^{a - i}) \\ &= p^a + \sum_{i = 0}^{a - 1} p^i (p - 1) p^{a - i - 1} \\ &= p^a + \sum_{i = 0}^{a - 1} p^{a - 1} (p - 1) \\ &= p^a + ap^{a - 1}(p - 1) \end{align*} $$

$n$ 太大，不能用筛法（在本题中也没有必要），但我们可以分解质因数计算啦。

总结：枚举 $\gcd$，内层变量外移，然后考虑作为 $\gcd$ 的次数，这是变形的常用方法。

【AC 代码】

#include <cstdio>
#include <cmath>

inline long long calc(long long p, long long a, long long pow){
    return a * (pow / p) * (p - 1) + pow;
}

int main(){
    long long n;

    scanf("%lld", &n);

    long long m = static_cast<long long>(ceil(sqrt(n) + 0.5));

    long long ans = 1;
    for(long long i = 2; i <= m; i++) if(n % i == 0){
        long long cnt = 0, pow = 1;
        while(n % i == 0) n /= i, cnt++, pow *= i;
        ans *= calc(i, cnt, pow);
    }

    if(n != 1){
        ans *= calc(n, 1, n);
    }

    printf("%lld\n", ans);

    return 0;
}

就是这样啦～