2190 - [SDOI2008]仪仗队

我们可以假设C君的位置为 $(0,0)$ ，建立一个平面直角坐标系。

那么队伍可以看做是一个 $(0,0)\rightarrow(n-1,n-1)$ 的 $n\times n$ 的矩阵。

我们可以不考虑 $(0,1)$ 和 $(1,0)$ ，最后在加上，就变成 $(1,1)\rightarrow(n-1,n-1)$ 的 $(n-1)\times(n-1)$ 的矩阵。

我们可以发现整个图形是对称的，所以只用算一半，乘上 $2$ ，再减去重复计算的 $(1,1)$ ，我们就来算满足 $b\leq a$ 的那一半。

我们可以发现，对于一个点 $(a,b)$ ，当 $\gcd(a,b)>1$ 时，会被 $(\dfrac{a}{\gcd(a,b)},\dfrac{b}{\gcd(a,b)})$ 挡住，例如 $(4,2)$ 会被 $(2,1)$ 挡住。（原理为相似三角形）

所以能看到的 $(a,b)$ 都有 $\gcd(a,b)=1$ 。

设 $f_a$ 表示满足 $(a,b)$ 能被看到的 $b$ 有几个（ $1\leq b\leq a\leq n-1$ ）。

则这一半的个数为 $\sum\limits_{a=1}^n f_a$ ，整个的答案就是 $2(\sum\limits_{a=1}^n f_a)-1+2=2(\sum\limits_{a=1}^n f_a)+1$ 。

由 $\gcd(a,b)=1,b\leq a$ 得， $f_a$ 就是表示小于等于 $n$ 且与 $n$ 互质的数的个数，即 $\varphi(a)$ ，那么我们就把 $\varphi$ 线性筛出来再求和即可。

注意要特判 $n=1$ 的情况

#include <bits/stdc++.h>
using namespace std;
const int MAXN=40005;
bool isp[MAXN];
int prime[MAXN],pcnt,phi[MAXN],ans;
void init(int n) {
	ans=phi[1]=1;
	for(int i=2; i<=n; ++i) {//线性筛phi
		if(!isp[i]) {
			prime[++pcnt]=i;
			phi[i]=i-1;
		}
		for(int j=1,x; j<=pcnt&&(x=prime[j]*i)<=n; ++j) {
			isp[prime[j]*i]=1;
			if(i%prime[j]) {
				phi[x]=phi[i]*phi[prime[j]];
			} else {
				phi[x]=phi[i]*prime[j];
				break;
			}
		}
		ans+=phi[i];//顺便求和
	}
}
int main() {
	int n,q;
	scanf("%d",&n);
	init(--n);
	printf("%d\n",n==0?0:ans*2+1);//特判0
	return 0;
}