题解 P2303 【[SDOi2012]Longge的问题】

· · 题解

题面非常简洁，求 \sum\limits_{i = 1}^n \gcd(i, n)

我们设 t(x) 为 1 - n 中与 n 的最大公因数为 x 的数的个数，即

t(x) = \sum_{i = 1}^n[\gcd(i, n) = x] = \sum_{i = 1}^{\lfloor\frac nx\rfloor}[\gcd(i, \lfloor\frac nx\rfloor) = 1]

考虑 \phi(x) = \sum\limits_{i = 1}^n[gcd(i, n) = 1]

即 t(x) = \phi(\lfloor\frac nx\rfloor)

由于\gcd(i, n) | n，考虑化简原式为：

\sum_{i = 1}^n\gcd(i, n) = \sum_{d|n}d\sum_{i = 1}^n[\gcd(i, n) = d] = \sum_{d|n}d\phi(\frac nd)

对于所有 d | n 可以在 O(\sqrt n) 的时间复杂度内枚举，\phi 函数可以在 O(\sqrt n) 的时间复杂度内求出，故时间复杂度为 O(因数个数 * \sqrt n)

#include <cstdio>
long long phi(long long n) {
    long long res = n;
    for(long long i = 2; i * i <= n; i++) {
        if(n % i == 0) res = res / i * (i - 1);
        while(n % i == 0) n /= i; 
    }
    if(n > 1) res = res / n * (n - 1);
    return res;
}
long long f(long long x) {
    long long res = 0LL, i = 1LL;
    for(; i * i < x; i++)
        if(x % i == 0) res += i * phi(x / i) + (x / i) * phi(i);
    if(i * i == x) res += i * phi(i);
    return res;
}
int main(int argc, char *argv[]) {
    long long n;
    scanf("%lld", &n);
    printf("%lld", f(n));
    return 0;
}