\(\LaTeX\)乱玩ing……这点东西能写出这一坨公式窝也是蛮拼的 =

BZOJ2705 [SDOI2012]Longge的问题

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数 \(N\)，你需要求出 \(\sum \operatorname{gcd}(i, N) (1 \le i \le N)\)。

令 \(p(k)\) 为满足 \(\operatorname{gcd}(i, N) = k\) 的 \(i\) 的个数

$$
\sum_{1\le i\le N}\operatorname{gcd}(i, N) = \sum_{k|n}k \cdot p(k)
$$

由于 \(\operatorname{gcd}(i, N) = k \Leftrightarrow \operatorname{gcd}(\frac i k, \frac N k) = 1\)，所以 \(p(k) = \phi(\frac N k)\) 其中 \(\phi\) 为欧拉函数

所以答案为

$$
\sum_{k|n}k \cdot p(k) = \sum_{k|n}k \cdot \phi(\frac N k)
$$

#include <stdio.h>
#include <math.h>
#define MAXN      (1ULL << 32)
#define MAXN_SQRT (1ULL << 16)

unsigned long long phi(unsigned long long n)
{
    unsigned long long ret = n;
    unsigned long long i;
    for (i = 2; i <= MAXN_SQRT; ++i) if (n % i == 0) {
        ret = ret / i * (i - 1);
        do n /= i; while (n % i == 0);
    }
    if (n > 1) ret = ret / n * (n - 1);
    return ret;
}

int main()
{
    unsigned long long n, sqrt_n, i, ans = 0;
    scanf("%llu", &n);
    sqrt_n = sqrt(n);
    for (i = 1; i <= sqrt_n; ++i)
        if (n % i == 0) ans += (i * phi(n / i) + n / i * phi(i));
    if (sqrt_n * sqrt_n == n)
        ans -= sqrt_n * phi(sqrt_n);
    printf("%llu\n", ans);
    return 0;
}