51nod 1239 欧拉函数之和【欧拉函数+杜教筛】

和bzoj 3944比较像，但是时间卡的更死

设\( f(n)=\sum_{d|n}\phi(d) g(n)=\sum_{i=1}^{n}f(i) s(n)=\sum_{i=1}^{n}\phi(i) \)，然后很显然对于mu\( g(n)=1\)，对于\( g(n)=n*(n+1)/2 \)，然后可以这样转化一下：

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

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

\[=\sum_{d=1}^{n}s(\left \lfloor \frac{n}{d} \right \rfloor)
\]

\[s(n)=g(n)-\sum_{d=2}^{n}s(\left \lfloor \frac{n}{d} \right \rfloor)
\]

然后递归求解即可。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const long long N=5000005,m=5000000,mod=1e9+7,inv2=500000004;

long long n,phi[N],q[N],tot,p[N];

bool v[N];

long long getp(long long x)

{

	return (x<=m)?phi[x]:p[n/x];

}

void wk(long long x)

{//cout<<x<<endl;

	if(x<=m)

		return;

	long long t=n/x;

	if(v[t])

		return;

	v[t]=1;

	long long w=x%mod;

	p[t]=w*(w+1)%mod*inv2%mod;//cout<<x<<" "<<t<<endl;

	for(long long i=2,la=1;la<x;i=la+1)

	{

		la=x/(x/i);

		wk(x/i);

		p[t]=(p[t]-getp(x/i)*(la-i+1)%mod)%mod;

	}

}

int main()

{

	phi[1]=1;

	for(long long i=2;i<=m;i++)

	{

		if(!v[i])

		{

			q[++tot]=i;

			phi[i]=i-1;

		}

		for(long long j=1;j<=tot&&i*q[j]<=m;j++)

		{

			long long k=i*q[j];

			v[k]=1;

			if(i%q[j]==0)

			{

				phi[k]=phi[i]*q[j];

				break;

			}

			phi[k]=phi[i]*(q[j]-1);

		}

	}

	for(long long i=2;i<=m;i++)

		phi[i]=(phi[i]+phi[i-1])%mod;

	scanf("%lld",&n);//cout<<n<<" "<<n%mod<<" "<<(n+1)%mod<<endl;

	//g=(n%mod)*((n+1)%mod)%mod*inv2%mod;//cout<<g<<endl;

	if(n<=m)

		printf("%lld\n",phi[n]);

	else

	{

		memset(v,0,sizeof(v));

		wk(n);

		printf("%lld\n",(p[1]%mod+mod)%mod);

	}

	return 0;

}

巴特西

51nod 1239 欧拉函数之和【欧拉函数+杜教筛】

最新文章

热门文章