终于学到了欧拉函数，咳出血。

---

有一个前置题目：。

上面这道题目问你平面上的两个点是否能够无阻碍地相互看见。

答案是横坐标差绝对值与纵坐标差绝对值，这两个数互质！

所以这道题也差不多，能看见的也只有互质的。

但是\(N \leq 40000\)，每个点算出gcd再判重好像有点慢。

其实有一种神奇的东西叫做欧拉函数\(\phi(n)\)，意思为小于等于\(n\)的正数中与\(n\)互质的数有多少个。

可以把这个正方形从对角线切开，然后分左上角和右下角分别计算。

不过因为这两边轴对称，所以答案是一样的，最后乘以2即可。

题解中看到了一句很点破题目的话：

y=0 只有原点(跳过)

y=1 找(x, 1)满足x < 1 且x与1互质

y=2 找(x, 2)满足x < 2 且x与2互质

...

y=N 找(x, N)满足x < N 且x与N互质

所以我们可以对一个三角形区域算一遍，而上面的东西不就是欧拉函数了吗？

所以从1到\(n-1\)我们把所有的欧拉函数值加一遍，最后乘以2，记得再加1（对角线也有一个点能被看见）。

问题来了：如何算欧拉函数？

那么我们来引入欧拉筛法，其实素数的线性筛就是从这里来的。

具体可以看这个博客，我肯定没他讲得细：。

然后注意特判\(n=1\)的情况，这个时候只有\(1 \times 1\)，只有他自己，答案为0。

欧拉筛里面有需要注意的地方，注意一下。

代码：

#include
    
     #include
     
      const int maxn = 40005;int n;bool isprime[maxn];int prime[maxn], tot;int phi[maxn];int ans;void get_phi(){    memset(isprime, true, sizeof isprime);    isprime[1] = false;    phi[1] = 1;        for(int i = 2; i <= n; i++)    {        if(isprime[i])        {            phi[i] = i - 1;            prime[++tot] = i;        }        for(int j = 1; j <= tot; j++)// no else        {            if(i * prime[j] > n) break;            isprime[i * prime[j]] = false;            if(i % prime[j] == 0)            {                phi[i * prime[j]] = phi[i] * prime[j];// attention                break;            }            else phi[i * prime[j]] = phi[i] * (prime[j] - 1);// attention        }    }}int main(){    scanf("%d", &n);    get_phi();        for(int i = 1; i < n; i++) ans += phi[i];    printf("%d\n", ans * 2 + 1);    return 0;}