BZOJ 2005 [Noi2010]能量采集

题目大意

求$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} (\gcd(i,j)-1)$.

需要用到的公式：$\sum\limits_{d|n} \varphi(d) = n$

难度适中的一道数论题= =

"-1"没啥用可以先去掉。之后就变成$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \gcd(i,j)$.

第一次变换：进行欧拉反演。 第二次变换：将$\varphi(d)$提出来统计贡献。

$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \gcd(i,j) = \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d|\gcd(i,j)} \varphi(d) = \varphi(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor$$

之后枚举d就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,prm[100001],cnt,phi[100001];
long long ans;
bool v[100001];
void init()
{
	int cnt=0;
	phi[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!v[i]) prm[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*prm[j]<=n;++j)
		{
			v[i*prm[j]]=true;
			if(i%prm[j]) phi[i*prm[j]]=phi[i]*(prm[j]-1);
			else
			{
				phi[i*prm[j]]=phi[i]*prm[j];
				break;
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	if(n>m) swap(n,m);
	init();
	for(int i=1;i<=n;++i)
		ans+=1ll*phi[i]*(n/i)*(m/i);
	printf("%lld\n",ans*2-1ll*n*m);
}