SP3871 GCDEX - GCD Extreme

LuoGu: SP3871 GCDEX - GCD Extreme

GCDEX - GCD Extreme

先计算：
$$\begin{array}{rl}f(n)=& \sum _{x=1}^n\sum _{y=1}^{n}gcd(x,y)\\ =& \sum _{x=1}^n\sum _{y=1}^n\sum _{d|gcd(i,j)}\phi (d)\\ =& \sum _{x=1}^n\sum _{y=1}^n\sum _{d|gcd(i,j)}\phi (d)\\ =& \sum _{d=1}^n\phi (d){\lfloor \frac{n}{d}\rfloor }^2\end{array}$$
考虑删去重复的部分。首先是 $i=j$ 的情况，$gcd(i,i)=i$ ，因此这部分重复的有 ${\displaystyle \sum _{i=1}^{n}i}$ ，即 $n(n+1)/2$ ，对于剩下的部分，因为 $i$ 和 $j$ 可以交换，所以计算了两次，除以 $2$ 即可。

查看代码

#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
bool vis[N];
LL cnt, primes[N];
LL phi[N], s[N];
void init()
{
    phi[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!vis[i])
        {
            primes[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * primes[j] < N; j++)
        {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * phi[primes[j]];
        }
    }
    for (int i = 1; i < N; i++)
        s[i] = s[i - 1] + phi[i];
}
int main()
{
    init();
    while (~scanf("%lld", &n))
    {
        if (!n)
            break;
        LL res = 0;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = n / (n / l);
            res += (s[r] - s[l - 1]) * (LL)(n / l) * (LL)(n / l);
        }
        printf("%lld\n", (res - (LL)n * (n + 1) / 2) / 2);
    }
    return 0;
}