[洛谷 2158][SDOI2008] 仪仗队【欧拉函数】

• 2018-03-01
• 0
• 0

Problem:

题目描述

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

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

输入输出格式

输入格式：

共一个数N

输出格式：

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

输入输出样例

4

9

数据规模和约定

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

Solution:

大水题。。我们发现点 (x, y) 能被观测到当且仅当 x 和 y 互质，否则若 GCD(x, y) = d > 1，则点 (x, y) 会被点 (x / d, y / d) 挡住。

故原题可转化为求 (N-1)×(N-1) 网格上两坐标互质的格点数加 3 【即点 (0, 1), (1, 0), (1, 1)】，也就是 3 + ∑_2≤i≤N-1 φ(i) 的值【φ(i) 为欧拉函数，即 1 ~ i-1 中与 i 互质的数的个数】。

直接用欧拉筛 O(N) 筛出 φ(1) ~ φ(N) 的值即可。

注意 N == 1 需要特判，直接输出 0 即可。

Code: O(N) [2363K, 0MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N, phi[40002], prime[40002], pcnt;
bool isprime[40002];

inline void calc_phi(int upr){
	memset(isprime, 1, sizeof(isprime)), pcnt = 0;
	for(register int i = 2; i <= upr; i++){
		if(isprime[i]) prime[++pcnt] = i, phi[i] = i - 1;
		for(register int j = 1; j <= pcnt && i * prime[j] <= upr; j++){
			isprime[i * prime[j]] = 0;
			if(i % prime[j] == 0){
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			else phi[i * prime[j]] = phi[i] * phi[prime[j]];
		}
	}
}

int main(){
	scanf("%d", &N);
	if(N == 1) return puts("0"), 0;  // Special judge for N == 1
	calc_phi(--N);
	int ans = 0;
	for(register int i = 2; i <= N; i++) ans += phi[i];
	printf("%d\n", ans * 2 + 3);
	return 0;
}