Luogu P2158 仪仗队 题解报告

题目传送门

【题目大意】

给定一个n×n的点方阵,求站在左下角的点能看到的点数

注意同一条直线上只能看到一个点

【思路分析】

因为是一个方阵,所以可以对称地算,那么对于半个方阵,这里假设是左上的半个方阵,能看到的点的个数要满足这样的条件

1.x<y

因为是左上的半个方阵,并且x=y的一直线上的点要额外计算

2.gcd(x,y)即x与y互质

这是为了保证一直线上只能看到一个点

容易发现,在满足条件的情况下,这样的x个数恰好等于φ(y)

还需要注意的一点是,最左边一列,最下面一行,还有x=y这条直线上一共可以看到三个点,所以要额外计算

于是最后的答案Ans=3+2*$\sum_{i=2}^{n}\varphi[i]$

【代码实现】

 #include<bits/stdc++.h>
#define go(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
const int N=;
int v[N],prime[N],phi[N];
int n;
int fr(){
int w=,q=;
char ch=getchar();
while(ch<''||ch>''){
if(ch=='-') q=-;
ch=getchar();
}
while(ch>=''&&ch<='')
w=(w<<)+(w<<)+ch-'',ch=getchar();
return w*q;
}
void work(){
memset(v,,sizeof(v));
int num=;
go(i,,n){
if(v[i]==){//如果i没有被标记过,那就是质数
v[i]=i,prime[++num]=i;
phi[i]=i-;//性质2
}
go(j,,num){
if(prime[j]>v[i]||prime[j]>n/i) break;
v[i*prime[j]]=prime[j];
phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-:prime[j]);
//性质8和性质9的结合
}
}
}
int ans=;
int main(){
n=fr();n--;
//这里要注意一下题目的bug,你可以认为输入的是点数但实际上是看格子
if(n==) {printf("0\n");return ;}
work();
go(i,,n)
ans+=phi[i];
ans*=;ans+=;
printf("%d\n",ans);
return ;
}

AC代码戳这里

上一篇:odoo开发环境搭建(四):python开发工具IDE pycharm配置


下一篇:vim温馨提示