记录编号	581777	评测结果	AAAAAAAAAA
题目名称	[SDOI 2008] 仪仗队	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-08-12 21:50:15	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 40010;
int n,tot,ans;
int phi[N],prim[N];
bool v[N];
int main(){
	freopen("bzoj_2190.in","r",stdin);
	freopen("bzoj_2190.out","w",stdout);
	scanf("%d",&n);
	phi[1] = 1,v[1] = 1;//!!φ(1)被定义为1 
	if(n == 1){
		printf("0\n") ;
		return 0;
	}
	//欧拉线性筛优化求欧拉函数φ(1)~ φ(n)
	for(int i = 2;i <= n;i++){
		if(!v[i]){
			prim[++tot] = i;
			phi[i] = i-1;
		}
		for(int j = 1;j <= tot && i * prim[j] <= n;j++){
			v[i*prim[j]] = 1;
			if(!(i % prim[j])){
				phi[i*prim[j]] = phi[i] * prim[j];
				break;
			}
			else phi[i*prim[j]] = phi[i] * phi[prim[j]];
			//积性函数
			//即若gcd(a,b)=1,则φ(ab) = φ(a)*φ(b) 
		}
	}
	for(int i = 1;i < n;i++)ans += phi[i];
	printf("%d\n",ans*2+1);
	
	return 0;
	
}