JZOJ 3927. 【NOIP2014模拟11.6】可见点数
2024-09-07 07:58:58
3927. 【NOIP2014模拟11.6】可见点数 (Standard IO)
Time Limits: 1000 ms Memory Limits: 65536 KB
Description
ZPS经过长期的努力争取,终于成为了0901班的领操员,他要带领0901班参加广播操比赛。现在0901班的队伍可以看作是一个n*n的点阵,每个人都站在格点上。现在作为领操员的ZPS站(0,0)点,他想知道如果0901班的队伍站齐了,他能看到多少个人的脸(假设每个人的身高相同,体积相同)。
Input
一个正整数n。
Output
ZPS能看到多少个人的脸(当然他是看不到自己的脸的)。
Sample Input
3
Sample Output
5
Data Constraint
40%的数据,n<=1500。
100%的数据,n<=100000。
题解
题目大意是求在 n∗n 的矩阵中有多少个点与(0,0)中间没有第三点
首先想到的是只要(x,y)满足gcd(x,y)=1就是要求的点
我们假设 x<y ,那么 ans/2−1=∑n−1i=1phi[i]
问题就变成了求 phi[i] 了
求 phi[i] 必须用线性筛,否则会超时
代码
#include<cstdio>
#define N 100005
long long phi[N];
long p[N],tot;
bool b[N];
int main()
{ long n,i,j;
long long ans=0;
scanf("%ld",&n);
if(n==1){
printf("0\n");
return 0;
}
phi[1]=1;
for(i=2;i<=n;i++){
if(!b[i]){
p[++tot]=i;
phi[i]=i-1;
}
for(j=1;j<=tot&&i*p[j]<=n;j++){
b[i*p[j]]=true;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}else phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
for(i=1;i<n;i++)
ans+=phi[i];
printf("%lld\n",ans*2+1);
return 0;
}
最新文章
- 用C#通过反射实现动态调用WebService 告别Web引用
- .net xml 增删改查基础复习及干货分享
- lib3ds类库
- (转)A Beginner&#39;s Guide To Understanding Convolutional Neural Networks
- JavaScript基础-流程控制-if
- ubuntu访问文件服务器
- 【编程技巧】 iOS 5的StoryBoard(故事板)的一些用法
- 【BZOJ2729】【HNOI2012】排队(组合数学)
- Ansible实战演练
- Java中的String为什么是不可变的? -- String源码分析
- chardet查看字符串的编码(非常好用)
- Oracle物化视图梳理
- QPointer,QSharedPointer,QWeakPointer的区别
- 第三个Sprint ------第一天
- tensorflow内存溢出问题
- js实现上传图片本地预览功能以及限制图片的文件大小和尺寸大小
- win7 默认程序设置
- Shader的基本用法和语法结构
- (转)web开发流程
- SpringBoot入门(1)