l
i
n
k
link
link
方阵是关于对角线对称的 所以只用求出半个方阵能看见的人 再
×
2
times 2
×2即可
还有
3
3
3个特殊点 即对角线和两边 有
3
3
3个
能被看见的人
(
i
,
j
)
(i,j)
(i,j) 需满足
g
c
d
(
i
,
j
)
=
1
gcd(i,j)=1
gcd(i,j)=1 因为他一定可以把所有
(
k
x
,
k
y
)
(kx,ky)
(kx,ky)挡住
然后欧拉函数
#include#include #include #include #include using namespace std; typedef long long ll; const int N=4e4+5; int phi[N],n,ans; void Prime(int n) { for(int i=1;i<=n;i++) phi[i]=i; for(int i=2;i<=n;i++) if(phi[i]==i) for(int j=i;j<=n;j+=i) phi[j]=phi[j]/i*(i-1); } int main() { scanf("%d",&n); Prime(n); for(int i=2;i
