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

  • 2018-03-01
  • 0
  • 0

Problem:

题目描述

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

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

输入输出格式

输入格式:

共一个数N

输出格式:

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

输入输出样例

输入样例#1:

4

输出样例#1:

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

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai