【bzoj2190】[SDOI2008]仪仗队 欧拉函数

时间:2021-03-16 16:49:40

题目描述

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

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

输入

共一个数N。

输出

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

样例输入

4

样例输出

9


题解

欧拉函数

将左下角的点的坐标视为(0,0),则如果一个除(0,1)和(1,0)以外点能够被看见,它的横纵坐标必定互质。

那么可以盖住左上半部分和对角线,那么每个横坐标i对应的能看到的点的个数就是φ(i)。

然后快筛欧拉函数即可。

别忘了还有(1,1)这个点,所以答案为2*∑φ(i)+1(1≤i<n)=2*∑φ(i)+3(2≤i<n)。

#include <cstdio>
#include <algorithm>
using namespace std;
int f[40010] , sta[40010] , tot;
bool p[40010];
int main()
{
int n , i , j , ans = 0;
scanf("%d" , &n);
for(i = 2 ; i < n ; i ++ )
{
if(!p[i]) sta[++tot] = i , f[i] = i - 1;
for(j = 1 ; j <= tot && i * sta[j] <= n ; j ++ )
{
p[i * sta[j]] = 1;
if(i % sta[j] == 0)
{
f[i * sta[j]] = f[i] * sta[j];
break;
}
else f[i * sta[j]] = f[i] * (sta[j] - 1);
}
ans += f[i];
}
printf("%d\n" , ans * 2 + 3);
return 0;
}