洛谷 P2398. GCD SUM

题目描述

求

$$\sum \limits _ {i = 1} ^ n \sum \limits _ {j = 1} ^ n \gcd(i, j)$$

输入:
2

输出:
5

算法1 线性筛 $O(n)$

将式子变形:

要知道一个前置定理
$\sum \limits _ {d | n} \varphi ( d ) = n$

艾弗森约定:
定义 $\\\ [P]$ = $$\begin{cases} P \text{ } is \text { }true \text{ }1 \\\ P \text{ }is \text{ }false \text{ }0 \end{cases}$$

$$\sum\limits _ {i = 1} ^ n \sum\limits _ {j = 1} ^ n \gcd(i, j)\\$$

$$=\sum\limits _ {i = 1} ^ n \sum\limits _ {j = 1} ^ n \sum \limits _ {k | \gcd ( i, j )} \varphi ( k )\\$$

$$=\sum \limits _ {i = 1} ^ n \sum \limits _ {j = 1} ^ n \sum \limits _ {k | i, k | j} \varphi ( k )\\$$

$$=\sum \limits _ {k = 1} ^ n \varphi ( k ) \sum \limits _ {i = 1} ^ n \sum \limits _ {j = 1} ^ n [k | i][k | j]\\$$

$$=\sum \limits _ {k = 1} ^ n \varphi ( k ) \lfloor \frac {n}{k} \rfloor \lfloor \frac {n}{k} \rfloor$$

就可以$O(n)$预处理欧拉函数然后$O(\sqrt n)$数论分块过掉了

$Code:$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

typedef long long LL;

int n;
int primes[N], cnt;
LL phi[N], sum[N];
bool st[N];

void init(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            phi[i] = i - 1;
        }
        
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    
    for (int i = 1; i <= n; i ++ )
        sum[i] = sum[i - 1] + phi[i];
}

int main()
{
    init(N - 1);
    
    scanf("%d", &n);
    LL res = 0;
    
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        res += (sum[r] - sum[l - 1]) * (n / l) * (n / l);
    }
    
    printf("%lld", res);
    
    return 0;
}