P2158 [SDOI2008]仪仗队

P2158 [SDOI2008]仪仗队

0x01 题意

给定一个(n imes n)的方阵，求左下角的点与其他点的连线中，不经过其他点（也就是只经过左下角的点和终点）的连线的个数

0x02 解

可以容易地发现，当我们以左下角的点为原点((0,0))，终点为((x,y))，且(gcd(x,y)=1)时，该连线只经过两个点。（其中(gcd(i,0)=gcd(0,i)=i)）

问题转化为求该方阵中所有坐标满足(gcd(x,y)=1)的点的个数，即：

[ans[1]=0 ]

[ans(n)=sum_{x=0}^{n-1}sum_{y=0}^{n-1}[gcd(x,y)=1],ngeq 2 ]

我们发现，所有满足条件的点都关于(y=x)对称，所以原式简化为：

[ans[n]=2sum_{x=0}^{n-1}sum_{y=0}^{x-1}[gcd(x,y)=1]+1,ngeq 2 ]

我们还回想起，寒假第一节课，有npy的yjc给我们讲了欧拉函数的知识

[phi(n)=sum_{i=0}^{n-1}[gcd(i,n)=1] ]

所以我们可以把式子再简化为：

[ans[n]=sum_{x=0}^{n-1}phi(x)+1,ngeq 2 ]

线性筛预处理，(O(n))扫一遍解决

0x03 码

#include<bits/stdc++.h>
using namespace std;
const int N=40010;

bool notp[N];
int cnt=0,phi[N],pri[N];
void getphi(int n){
	cnt=0;
	notp[1]=1,phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!notp[i]) pri[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&pri[j]*i<=n;j++){
			notp[pri[j]*i]=1;
			if(i%pri[j]==0){phi[pri[j]*i]=phi[i]*pri[j];break;}
			else phi[pri[j]*i]=phi[i]*(pri[j]-1);
		}
	}
}

int main(){
	int n;
	getphi(40010);
	cin>>n;
	
	if(n==1){cout<<0;return 0;}
	
	long long ans=0;
	
	for(int i=0;i<n;i++){
		ans+=phi[i];
	}
	
	cout<<2*ans+1;
	
	return 0;
}