首页 > 题解 > bzoj 2190 [SDOI2008]仪仗队

bzoj 2190 [SDOI2008]仪仗队

Description

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

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

Input

  共一个数N。

Output

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

Sample Input

  4

Sample Output

  9

HINT

【数据规模和约定】   对于 100% 的数据,1 ≤ N ≤ 40000

题解

如果按对角线剖分的话,两边可以看到的学生数都恰好是1~n-1范围内的互质数对数,即$\sum \varphi(i)$

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 40000;
bool p[N + 10];
int n, T;
unsigned long long phi[N + 10], pr[N + 10];
void init(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!p[i])
            pr[++pr[0]] = i, phi[i] = i - 1;
        for (int j = 1; j <= pr[0] && i * pr[j] <= n; ++j) {
            p[i * pr[j]] = 1;
            if (i % pr[j] == 0) {
                phi[i * pr[j]] = phi[i] * pr[j];
                break;
            }
            phi[i * pr[j]] = phi[i] * phi[pr[j]];
        }
    }
    for (int i = 1; i <= n; ++i) phi[i] += phi[i - 1];
}
main() {
    scanf("%d", &n);
    if (n < 2) {
        puts("0"); return 0;
    }
    init(n);
    printf("%lld\n", (phi[n - 1] - phi[1] + 2) * 2ll - 1ll);
}