Rockdu's Blog

题目描述

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

输入输出格式

共一个数N

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

输入输出样例

4

9

说明

【数据规模和约定】

对于 100% 的数据，1 ≤ N ≤ 40000

考虑对于一个矩形，站在左下角如何才能看到右上角的人？不难发现，如果有遮挡，那么说明对角线上有点，而对角线上有点的情况说明以原左下角点和该点为界的矩形可以通过倍数扩展到当前矩形。那如果要没有人遮挡，一定需要长宽互质。很容易想到欧拉函数 + 筛法。下面贴一段代码：

#include<cstdio>
using namespace std;
const int maxn = 40005;
int pri[maxn], phi[maxn], ans;
bool vis[maxn];
void pre_phi(int N) {
    phi[1] = 1, vis[1] = 1;
    for(register int i = 2; i <= N; ++i) {
        if(!vis[i]) phi[i] = i - 1, pri[++pri[0]] = i;
        for(register int j = 1; j <= pri[0] && i * pri[j] <= N; ++j) {
            phi[i * pri[j]] = phi[i] * phi[pri[j]];
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];/*核心代码，用心感受*/
                break;
            }
        }
        ans += phi[i];
    }
}

int main() {
    int n;
    scanf("%d", &n);
    pre_phi(n - 1);
    printf("%d", ans * 2 + 3);
    return 0;
}