[SDOI2008]仪仗队

题目：BZOJ2190、洛谷P2158、codevs2296。

题目大意：有一个$n×n$的矩形仪仗队，一个人站在左下角，要你求他能看到多少其他同学。

解题思路：我们假设那个人的位置为(0,0)，那么可以发现，所有他能看到的同学的x,y坐标互质。那么我们可以以对角线将整个矩阵分成两半，问题就转化为求i=2~n-1中比i小的且与i互质的数的总数(即$sum_{i=2}^{n-1}varphi(i)$)，就是求欧拉函数，最后乘2加上(0,1)(1,0)(1,1)这三个即可。

求欧拉函数我们可以用类似判断素数的方法，在$O(sqrt n)$的时间内求出。

于是时间复杂度为$O(nsqrt n)$。

C++ Code：

#include<cstdio>
using namespace std;
int n;
int main(){
	scanf("%d",&n);
	int ans=0;
	for(int i=2;i<n;++i){
		int e=i,p=i;
		for(int j=2;j*j<=i;++j){
			if(p%j==0){
				e-=e/j;
				while(p%j==0)p/=j;
			}
		}
		if(p>1)e-=e/p;
		ans+=e;
	}
	printf("%d
",ans*2+3);
	return 0;
}