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);
}