题目：

给一个由学生组成的 $n*n$ 的方阵，求在一个角可以看到的学生人数。

思路：

我们将左下角的位置标为 $(0,0)$，向右为 x 正方向，向上为 y 正方向。

规律的寻找和证明

围绕着角的三个点，即 $(1,0)$, $(1,1)$, $(0,1)$ 显然都可以被看到，而对于其他的点来说，某个点可以被看到当且仅当 x y 互质。

我们可以做以下证明：取某一个位置并与原点连线，形成的直线是 $y=kx$。如果这个点 x y 不互质，则可以同时除以它们的最大公约数 p，得到 $\frac{x}{p}=k\frac{y}{p}$——显然$(\frac{y}{p},\frac{x}{p})$ 也在直线 $y=kx$ 上而且距离原点更近。这样就导致在看到 $(x,y)$ 之前先看到了 $(\frac{y}{p},\frac{x}{p})$，这样 $(x,y)$ 就看不到了。

题目的转换

因为方阵关于对角线对称，其左上和右下可以看到的点数是相同的，所以只需要求其中的一侧，最后再乘以二就可以了。我们现在来看对角线左上的点：根据之前所得到的性质，我们要找出所有 x y 互质的点的个数。对角线左上的点都有 $x<y$，那么对于每一行就是要求比 y 小而且与 y 互质的点的个数——是不是听着耳熟？这不是就是欧拉函数 $\varphi(y)$? 于是我们就将原题变成一个计算题：$Answer=3+2*\Sigma^{n}_{i=2}\varphi(i)$

欧拉函数的计算

计算欧拉函数，我们需要使用它的两条性质：

• $p$ 为素数，若 $p\mid n$ 且 $p^2\mid n$，则有 $\varphi(n)=\varphi(n/p)*p$
• $p$ 为素数，若 $p\mid n$ 但 $p^2\nmid n$，则有 $\varphi(n)=\varphi(n/p)*(p-1)$

我们可以利用线性筛法每个合数 $n$ 只被其最小素因子 $p$ 筛一次的特点（不会线性筛法?），将原公式变为 $\varphi(n*p)=\varphi(n)p$ 和 $\varphi(np)=\varphi(n)*p$。至此，我们有了求欧拉函数的方法，这道题也就迎刃而解了。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MaxN = 40000 + 5;
int n, answer;
int phi[MaxN], minimizedPrimeFactor[MaxN], primeNumber[MaxN], primeCount;
void Eular(int n){
	memset(minimizedPrimeFactor,0,sizeof(minimizedPrimeFactor));
	primeCount = 0;
	for(int i = 2; i <= n; i++){
		if(minimizedPrimeFactor[i] == 0){
			minimizedPrimeFactor[i] = i;
			primeNumber[++primeCount] = i;
			phi[i] = i-1;
		}
		for(int j = 1; j <= primeCount; j++){
			if(primeNumber[j] > minimizedPrimeFactor[i] || primeNumber[j] > n/i) break;
			minimizedPrimeFactor[i * primeNumber[j]] = primeNumber[j];
			phi[i * primeNumber[j]] = phi[i] * (i % primeNumber[j]? primeNumber[j] - 1 : primeNumber[j]); 
            //注意这里三目运算结果的顺序
		}
	}
	return;
}
int main(){
	scanf("%d",&n);
	if(n == 1){
		printf("0");
		return 0;
	}
	Eular(n);
	for(int i = 2; i < n; i++) answer+=phi[i];
	printf("%d\n",answer*2+3);
	return 0;
}

为什么只需要i % primeNumber[j]？ 因为 i 是合数，已经有一个因子是 primeNumber[j]了。

值得注意的是三目运算时两个结果的顺序：取模运算结果为 0 是整除，对应第一条性质；结果为 1 是不整除，对应第二条性质（我才不会说第一遍写错而且看了好久也没看出来QWQ）。