[洛谷 2158][SDOI2008] 仪仗队【欧拉函数】
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; }
发表评论