LYDSY 2818

题目大意

暂无

题目解法

暂无

RTFC

#include <cstdio>
typedef long long int64;
const int maxn = 10000010;
int n, phi[maxn], prime[700010], pcnt;
int64 sum[maxn];
bool notPrime[maxn];
int main()
{
    scanf("%d", &n);
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        if (!phi[i])
            for (int j = i; j <= n; j += i)
            {
                if (!phi[j]) phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
    for (int64 i = 2; i <= n; i++)
        if (!notPrime[i])
            for (int64 j = i * i; j <= n; j += i)
                notPrime[j] = true;
    for (int i = 2; i <= n; i++)
        if (!notPrime[i])
            prime[pcnt++] = i;
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + phi[i];
    int64 ans = 0;
    for (int i = 0; i < pcnt; i++)
        ans += (sum[n / prime[i]] << 1) - 1;
    printf("%lld", ans);
    return 0;
}