【bzoj2190】 SDOI2008—仪仗队

http://www.lydsy.com/JudgeOnline/problem.php?id=2190 (题目链接)

题意

  一个N*N的方阵,问右下角的人能看到几个人。

Solution

  如果一个人(x,y)要被看到,那么当且仅当gcd(x,y)=1,否则的话,一定存在一个人(x/gcd(x,y),y/gcd(x,y))挡住了看向这个人的视线。

  这样一来,求得就是1~N范围内的互质数对了,欧拉函数前缀和搞一下,*2+1即可。

细节

  注意边界

代码

// bzoj2190
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=40010;
int phi[maxn],p[maxn],vis[maxn],n,tot; void calphi() {
phi[1]=1;
for (int i=2;i<=n;i++) {
if (!vis[i]) {p[++tot]=i;phi[i]=i-1;}
for (int j=1;j<=tot;j++) {
if (i*p[j]>n) break;
vis[i*p[j]]=1;
if (i%p[j]==0) {phi[i*p[j]]=phi[i]*p[j];break;}
else phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
int main() {
scanf("%d",&n);
calphi();
int ans=0;
for (int i=1;i<n;i++) ans+=phi[i];
printf("%d",2*ans+1);
return 0;
}

  

上一篇:贪心水题。UVA 11636 Hello World,LA 3602 DNA Consensus String,UVA 10970 Big Chocolate,UVA 10340 All in All,UVA 11039 Building Designing


下一篇:ASP.NET MVC常见问题解决方法