本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-21 11:28:49

难度：$\color{blue}\text{提高+/省选-}$

前言：

这题是蓝题但是很水

题目分析：

瞄一眼就能发现这个方阵可以被左下---右上对角线分成对称的两部分（中间的对角线是单独的一部分，单独计算）。就只看下面那半部分好了，可以发现，对于第 $i$ 列（$i \ge 2$，从左数），能看到的人数就是 $\phi(i-1)$。所以这半部分总共能看到的人数就是 $\Sigma_{i=2}^{n}\phi(i-1)$。
另一部分和这一部分的答案一样。至于剩下的那个对角线，可以发现对角线上肯定只有第一个人能被看见。
所以上下两部分加上对角线总共能看到的人数就是：
$2\cdot \Sigma_{i=2}^{n}\phi(i-1)+1$
复杂度：$\Theta(n\sqrt{n})$

特殊情况：

如果 $n = 1$，那么答案应该为 $0$，要特判一下。

欧拉函数：

设一个数为 $x$，欧拉函数就是求有多少个数 $i$ $(1 \le i \le x)$，与 $x$ 互质 $(gcd(i,x)=1)$ 。 记作 $\phi(x)$。
放上个求 $\phi(x)$ 的板子：

int eular(int n)
{
    int ret=1;
    for(reg int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n\/=i;
            ret*=(i-1);
            while(n%i==0)
            {
                n\/=i;
                ret*=i;
            }
        }
    }
    if(n>1)ret*=n-1;
    return ret;
}

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
#define reg register
int n;
int eular(int n)
{
    int ret=1;
    for(reg int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n\/=i;
            ret*=(i-1);
            while(n%i==0)
            {
                n\/=i;
                ret*=i;
            }
        }
    }
    if(n>1)ret*=n-1;
    return ret;
}
signed main()
{
    scanf("%lld",&n);
    if(n==1)
    {
        printf("0");
        return 0;
    }
    int ans=0;
    for(reg int i=2;i<=n;i++)
    {
        ans+=eular(i-1);
    }
    ans=(ans<<1)+1;
    if(ans<0)return -1;
    printf("%d",ans);
    return 0;
}