Sum

题意

给定正整数(n)，求(sum^n_iphi(i),sum^n_imu(i))。

---

思路

由于数据范围过大，本题采用杜教筛解决，在正确的预处理下，可以达到(O(n^{frac{2}{3}}))的优越复杂度。

假定对于积性函数(f(i))，我们需要求(S(n)=sum^n_if(i))

我们假定存在另一个积性函数(g)，那么(sum^n_i(f*g)(i)=sum^n_isum_{d|i}f(d)g(frac{i}{d}))

将(g(d))提出来就可以得到(sum^n_dg(d)S(frac{n}{d}))

那么(g(1)S(d)=sum^n_{i=1}g(i)S(frac{n}{i})-sum^n_{i=2}g(i)S(frac{n}{i}))

于是我们可以进行(O(1))求解，查询记忆化即可。

当然光记忆化还是不行，所以我们可以选择预处理一部分，剩下的大的记忆化。

据证明，预处理(n^{frac{2}{3}})时时间复杂度最优。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

	template<typename T> inline void read (T &x) {
		x=0;T f=1;char c=getchar();
		for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
		for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
		x*=f;
	}
	template<typename T> inline void write (T x) {
		if (x<0) putchar('-'),x=-x;
		if (x>=10) write(x/10);
		putchar(x%10+'0');
	}

}

using namespace StandardIO;

namespace Solve {
	
	const int N=5000000;
	
	static int T,cnt;
	static int isprime[N+5],prime[N+5],mu[N+5];
	static long long phi[N+5];
	static unordered_map<int,long long> rem_phi;
	static unordered_map<int,int> rem_mu;
	
	inline void init () {
		mu[1]=phi[1]=1;
		for (register int i=2; i<=N; ++i) {
			if (!isprime[i]) {
				prime[++cnt]=i,phi[i]=i-1,mu[i]=-1;
			}
			for (register int j=1; j<=cnt&&prime[j]*i<=N; ++j) {
				int k=prime[j]*i;
				isprime[k]=1;
				if (i%prime[j]==0) {
					mu[k]=0;
					phi[k]=phi[i]*prime[j];
					break;
				}
				phi[k]=phi[i]*phi[prime[j]];
				mu[k]=-mu[i];
			}
		}
		for (register int i=1; i<=N; ++i) {
			phi[i]+=phi[i-1],mu[i]+=mu[i-1];
		}
	}
	inline long long calc_phi (int x) {
		if (x<=N) return phi[x];
		if (rem_phi[x]) return rem_phi[x];
		long long ans=(long long)x*(x+1)/2;
		for (register int l=2,nxt; nxt<2147483647&&l<=x; l=nxt+1) {
			nxt=min(x,x/(x/l));
			ans-=(long long)(nxt-l+1)*calc_phi(x/l);
		}
		return rem_phi[x]=ans;
	}
	inline int calc_mu (int x) {
		if (x<=N) return mu[x];
		if (rem_mu[x]) return rem_mu[x];
		int ans=1;
		for (register int l=2,nxt; nxt<2147483647&&l<=x; l=nxt+1) {
			nxt=min(x,x/(x/l));
			ans-=(nxt-l+1)*calc_mu(x/l);
		}
		return rem_mu[x]=ans;
	}

	inline void MAIN () {
		init();
		read(T);
		while (T--) {
			int x;read(x);
			write(calc_phi(x)),putchar(' '),write(calc_mu(x)),putchar('
');
		}
	}
	
}

int main () {
	Solve::MAIN();
}