首页 > 代码库 > 【bzoj2190】[SDOI2008]仪仗队
【bzoj2190】[SDOI2008]仪仗队
题目描述
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 
现在，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;
}
【bzoj2190】[SDOI2008]仪仗队
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。