[BZOJ2190/Luogu2158][SDOI2008]仪仗队

题目链接：

BZOJ2190

Luogu2158

首先，对于((x,y)(x>1,y>1))，若(x,y)互质，则((x,y))合法。

因为矩形是对称的，那么可以把矩形分成两半分别统计，最后答案(*2)。

那么当(x)确定时，只需求出有多少(y(yle x),y)与(x)互质即可，标准的欧拉函数。

要特判(1)的情况。

时间复杂度 (O(nln n))

#include <cstdio>

int n,Phi[40005];

int main()
{
	scanf("%d",&n);
	if(n==1)return puts("1"),0;
	for(int i=2;i<=n;++i)
		if(!Phi[i])
			for(int j=i;j<=n;j+=i)
			{
				if(!Phi[j])Phi[j]=j;
				Phi[j]=Phi[j]/i*(i-1);
			}
	long long s=0;
	for(int i=2;i<n;++i)s+=Phi[i];
	printf("%lld
",(s<<1)+3);//x=1或y=1的有3个
	return 0;
}