solution

· · 题解

第一次看到这一题时，觉得是一道数论题，就手推了一下。

0是看不到，1是看得到。

n=1
0

n=2
11
01

n=3
010
111
010

n=4
0110
0101
1111
0100

n=5
01010
01101
01010
11111
01000
……

有没有发现什么？

（没有）

4 0 1 0 1 0
3 0 1 1 0 1
2 0 1 0 1 0
1 1 1 1 1 1
0 0 1 0 0 0
  0 1 2 3 4

如果我们将它标号，会发现所有除第0行或第0列以外，所有能被看到的同学的坐标是互质的，即：

点P(x,y)能被看到
则有(x,y)=1

所以就有了下面的暴力做法

for(int i=1;i<n;++i){
    for(int j=1;j<n;++j){
        if(gcd(i,j)==1) ++ans;
    }
}
ans+=2;

提交，T了,36分。

又得改进这究竟是人性的扭曲，还是道德的沦丧？

所以，根据坐标互质这个特点，我们就有了应用欧拉函数的思路

函数内容：（引用自百度百科）

对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目

我们就可以利用欧拉函数，在O(n)的时间内完成求解

因此，我们只需要求出从1~n的欧拉函数值，就能A掉题目

最终代码：

#include<cstdio>
using namespace std;
const int N=40001;
bool prime[N];
int m[N],phi[N],p[N],nump,n,ans;
void make()
{
    phi[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!m[i])
        {
            p[++nump]=i;
            phi[i]=i-1;
        }
        for (int j=1;j<=nump&&p[j]*i<n;j++)
        {
            m[p[j]*i]=1;
            if (i%p[j]==0)
            {
                phi[p[j]*i]=phi[i]*p[j];
                break;
            }
            else phi[p[j]*i]=phi[i]*(p[j]-1);
        }
    }
}
int main()
{
    scanf("%d",&n);
    if(n==1){
        printf("0");
        return 0;
    }
    make();
    for(int i=2;i<n;++i){
        ans+=phi[i];
    }
    ans*=2;
    ans+=3;
    printf("%d",ans);
    return 0;
}

注意：这里在写的时候使用的是欧拉筛法。如果使用O(n^2)的普通筛法就有可能会TLE