Description

作为体育委员, C 君负责这次运动会仪仗队的训练. 仪仗队是由学生组成的 \(n \times n\) 的方阵, 为了保证队伍在行进中整齐划一, C 君会跟在仪仗队的左后方, 根据其视线所及的 学生人数来判断队伍是否整齐 (如下图).

现在, C 君希望你告诉他队伍整齐时能看到的学生人数.

Input

共一个数 \(n\).

Output

共一个数, 即 C 君应看到的学生人数.

Sample Input

4

Sample Output

9

Data Range

对于 100% 的数据,\(1 \leq n \leq 40000\)

Explanation

令答案为 \(res\), 则能看到的点的横纵坐标一定互质, 那么:

\[res = \sum_{i=2}^{n-1} 2 \phi(i) + 3\]

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 40010;

int n;
int phi[maxn], prime[maxn];
bool vis[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    // Retrieve table of phi functions
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++prime[0]] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= prime[0]; j++) {
            if (i * prime[j] > n)
                break;
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
    // Getting result
    int res = 0;
    for (int i = 1; i < n; i++)
        res += phi[i];
    res = res * 2 + 1;
    printf("%d\n", res);
    return 0;
}