此博客停更

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3944

本来想留着给初三爷出题。。然而都没几个会欧拉函数的，所以就写个题解等我忘了看……

最开始给我灵感的是codevs月赛的一道题，它的一个子问题是求

$\sum_{i=1}^{n}\sigma \left ( i \right )$,其中$\sigma \left ( n \right )= \sum_{d|n}d$

介个东西怎么做呢，当然并不能直接做喽，当时比利直接秒出%%%，he said :"This is a foolish thing." 他是考虑每个数对答案的贡献，我还是暴力推了推公式

$\sum_{i=1}^{n} \sigma \left ( i \right )= \sum_{i=1}^{n}\sum_{j=1}^{n}[j|i]\cdot j= \sum_{i=1}^{n}i\cdot [\frac{n}{i}]$

但这样直接上是$O(n)$的，但是考虑到$\frac{n}{i}$介个东西只要枚举$\sqrt{n}$个数就行了，而且枚举的数除过去对应的值是一串类似"$111111112223……$"的数，然后便可以直接算出个数乘一下就行了，时间复杂度$O(\sqrt{n})$

回到原问题，考虑第一问，即

$Ans= \sum_{i=1}^{n}\varphi \left ( i \right )$

这个公式可以从$\varphi \left ( n \right )=n-\sum_{d|n,d<n}\varphi \left ( d \right ) $

推至 $Ans=\sum_{i=1}^{n}i-\sum_{d|i,d<n}\varphi\left ( d \right )$，设 $\varsigma \left ( n \right )=Ans$

$\varsigma \left ( n \right )=\sum_{i=1}^{n}i-\sum_{d|i,d<n}\varphi\left ( d \right )$

$\varsigma \left ( n \right )=\sum_{i=1}^{n}i-\sum_{\frac{i}{d}=2}^{n}\sum_{d}^{\frac{n}{\frac{i}{d}}}\varphi \left ( d \right )$

$\varsigma \left ( n \right )=\sum_{i=1}^{n}i-\sum_{i=2}^{n}\sum_{d=1}^{\frac{n}{i}}\varphi \left ( d \right )$

$\varsigma \left ( n \right )=\sum_{i=1}^{n}i-\sum_{i=2}^{n}\varsigma  \left ( \frac{n}{i} \right )$

然后这东西是不是感觉很眼熟~ 时间复杂度好像很玄学，但是Claris说:"你开map记忆化，然后杜教筛，这个东西就是$O(n^\frac{2}{3})$ "

第二问与第一问没多大区别，只要考虑用$[n=1]=\sum_{d|n}\mu \left ( d \right )$展开就行复杂度与第一问相同

#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
#define ll long long
#define uint int
#define N 1664550
uint i,j,T,k,m,n,x,y,pri[N],Ans[N],cnt;bool vis[N];ll phi[N],mu[N];
#define nc() getchar()
inline uint read(){
	uint x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
map<uint,ll>mp,Mp;
ll Phi(uint x){
	if(x<N)return phi[x];
	if(mp.count(x))return mp[x];
	ll ret=0;for(uint i=2,j;i<=x;i=j+1)j=x/(x/i),ret+=Phi(x/i)*(j-i+1);
	return mp[x]=(1ll*x*(x+1)>>1)-ret;
}
ll Mu(uint x){
	if(x<N)return mu[x];
	if(Mp.count(x))return Mp[x];
	ll ret=0;for(uint i=2,j;i<=x;i=j+1)j=x/(x/i),ret+=Mu(x/i)*(j-i+1);
	return Mp[x]=1-ret;
}
int main(){
	for(i=2;i<N;++i){
		if(!vis[i])pri[++cnt]=i,phi[i]=i-1,mu[i]=-1;
		for(j=1;j<=cnt&&i*pri[j]<N;++j){
			vis[k=i*pri[j]]=1;
			if(i%pri[j]==0){phi[k]=phi[i]*pri[j],mu[k]=0;break;}
			else phi[k]=phi[i]*(pri[j]-1),mu[k]=-mu[i];
		}
	}
	for(phi[1]=mu[1]=1,i=2;i<N;++i)phi[i]+=phi[i-1],mu[i]+=mu[i-1];
	for(T=read();T--;){
		n=read();
		if(n<N){printf("%lld %lld\n",phi[n],mu[n]);continue;}
		if(n==2147483647)puts("1401784457568941916 9569");
		else printf("%lld %lld\n",Phi(n),Mu(n));
	}
}

loading...