题目:
给一个n,n的网格,点可以遮挡视线,问从0,0看能看到多少点
题解:
根据对称性,我们可以把网格按y=x为对称轴划分成两半,求一半的就可以了,可以想到的是应该每种斜率只能看到一个点
因为斜率表达式k=y/x,所以直线上的点都满足这个关系,那么显然当gcd(x,y)==1的时候这个点是直线上的第一个点,其他点的坐标一定是这个点的若干倍
所以问题转化成求gcd(x,y)==1的点对个数,即∑phi[i](1<=i<=n)
欧拉函数即可
#include<cstdio>
using namespace std;
int n,t,ans;
int oula(int n)
{
int ans=n,a=n;
for(int i=;i*i<=n;i++)
{
if(a%i==)
{
ans-=ans/i;
while(a%i==)
a/=i;
}
}
if(a>) ans-=ans/a;
return ans;
}
int main()
{
scanf("%d",&t);
for (int i=;i<=t;i++)
{
ans=;
scanf("%d",&n);
for (int j=;j<=n;j++)
ans+=oula(j);
printf("%d %d %d\n",i,n,ans*+);
}
return ;
}