luogu P1447 [NOI2010]能量采集欧拉反演

题面

题目要我们求的东西可以化为：

\[\sum_{i=1}^{n}\sum_{j=1}^{m}2*gcd(i,j)-1
\]

\[-nm+2\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)
\]

\(\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)=\)

\[\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j}\phi(d)
\]

\[\sum_{d=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor}\phi(d)
\]

\[\sum_{d=1}^{n}\phi(d){\lfloor\frac{n}{d}\rfloor}{\lfloor\frac{m}{d}\rfloor}
\]

所以原式为：

\[-nm+2\sum_{d=1}^{n}\phi(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
\]

暴力枚举\(d\)计算即可

PS：这类带有\(gcd(i,j)\)的式子用欧拉反演会比暴力枚举约数方便很多，比如说这题

代码：

#include<bits/stdc++.h>

using namespace std;

#define N 100007

#define ll long long

const int lim=1e5;

int pr[N],cnt,phi[N];

bool zhi[N];

void Init()

{

	int i,j;

	phi[1]=1;

	for(i=2;i<=lim;i++)

	{

		if(!zhi[i])pr[++cnt]=i,phi[i]=i-1;

		for(j=1;j<=cnt&&i*pr[j]<=lim;j++)

		{

			int p=pr[j],x=i*p;

			zhi[x]=true;

			if(i%p==0){phi[x]=phi[i]*p;break;}

			phi[x]=phi[i]*(p-1);

		}

	}

}

int main()

{

	int n,m,i;

	ll ans=0;

	Init();

	scanf("%d%d",&n,&m);

	ans=-1ll*n*m;

	ll sum=0;

	for(i=1;i<=n;i++)

		sum+=1ll*phi[i]*(n/i)*(m/i);

	ans+=2*sum;

	printf("%lld\n",ans);

	return 0;

}

巴特西

luogu P1447 [NOI2010]能量采集欧拉反演

最新文章

热门文章

巴特西

luogu P1447 [NOI2010]能量采集 欧拉反演

最新文章

热门文章

luogu P1447 [NOI2010]能量采集欧拉反演