BZOJ 2818 Gcd

题目大意

给定整数N，求1<=x,y<=N且gcd(x,y)为素数的数对(x,y)有多少对.

这道题一看就明白，如果有$(X,Y)$使得$gcd(i,j) = P_i$那么就有$gcd(\frac{i}{P_i},\frac{j}{P_i}) = 1$，所以也就转化成了求小于$\lfloor\frac{n}{P_i}\rfloor$的所有互质数对个数。互质个数……一看就是$phi()$啊！

最终答案$ans=\sum\limits_{i=1}^{tot} \sum\limits_{j=1}^{\lfloor{\frac{n}{P_i}}\rfloor} \varphi(j)$.

#include <cstdio>
#include <algorithm>
using namespace std;
int n,cnt;
long long phi[10000010],prime[10000010],ans;
int use[10000010];
void geteular()
{
	phi[1]=1,use[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!use[i]) prime[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*prime[j]<=n;++j)
		{
			use[i*prime[j]]=1;
			if(!(i%prime[j]))
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}
int main()
{
	scanf("%d",&n);
	geteular();
	for(int i=1;i<=n;++i) use[i]=use[i-1]+(use[i]^1);
	for(int i=1;i<=n;++i) ans+=phi[i]*(use[n/i]);
	ans=(ans<<1)-use[n];
	printf("%lld\n",ans);
	return 0;
}