Description

Input

一共T+1行

第1行为数据组数T(T<=10)

第2~T+1行每行一个非负整数N，代表一组询问

Output

一共T行，每行两个用空格分隔的数ans1,ans2

Sample Input

6

1

2

8

13

30

2333

Sample Output

1 1

2 0

22 -2

58 -3

278 -3

1655470 2

Solution

杜教筛裸题啊

对于 \(\mu\) ，利用与它有关的卷积 \(\mu*1=e\) ，杜教筛式子为 \(S(n)=1-\sum_{i=2}^nS(\lfloor\frac{n}{i}\rfloor)\)

对于 \(\varphi\) ，利用与它有关的卷积 \(\varphi*1=id\) ，杜教筛式子为 \(S(n)=\sum_{i=1}^ni-\sum_{i=2}^nS(\lfloor\frac{n}{i}\rfloor)\)

#include<bits/stdc++.h>

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

const int MAXN=3000000+10;

int t,n,vis[MAXN],prime[MAXN],cnt,phi[MAXN],mu[MAXN],smu[MAXN];

ll sphi[MAXN];

std::map<int,int> M;

std::map<int,ll> P;

namespace IO

{

    const ui Buffsize=1<<15,Output=1<<23;

    static char Ch[Buffsize],*S=Ch,*T=Ch;

    inline char getc()

	{

		return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);

	}

    static char Out[Output],*nowps=Out;

    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

    template<typename T>inline void read(T&x)

	{

		x=0;static char ch;T f=1;

		for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;

		for(;isdigit(ch);ch=getc())x=x*10+(ch^48);

		x*=f;

	}

	template<typename T>inline void write(T x,char ch='\n')

	{

		if(!x)*nowps++='0';

		if(x<0)*nowps++='-',x=-x;

		static ui sta[111],tp;

		for(tp=0;x;x/=10)sta[++tp]=x%10;

		for(;tp;*nowps++=sta[tp--]^48);

		*nowps++=ch;

	}

}

using namespace IO;

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline void init()

{

	memset(vis,1,sizeof(vis));

	vis[0]=vis[1]=0;

	phi[1]=mu[1]=1;

	for(register int i=2;i<MAXN;++i)

	{

		if(vis[i])

		{

			prime[++cnt]=i;

			mu[i]=-1;phi[i]=i-1;

		}

		for(register int j=1;j<=cnt&&i*prime[j]<MAXN;++j)

		{

			vis[i*prime[j]]=0;

			if(i%prime[j])

			{

				mu[i*prime[j]]=mu[i]*mu[prime[j]];

				phi[i*prime[j]]=phi[i]*phi[prime[j]];

			}

			else

			{

				phi[i*prime[j]]=phi[i]*prime[j];

				break;

			}

		}

	}

	for(register int i=1;i<MAXN;++i)smu[i]=smu[i-1]+mu[i],sphi[i]=sphi[i-1]+phi[i];

}

inline int Smu(ll x)

{

	if(x<MAXN)return smu[x];

	if(M.find(x)!=M.end())return M[x];

	int res=0;

	for(register ll i=2;;)

	{

		if(i>x)break;

		ll j=x/(x/i);

		res+=(j-i+1)*Smu(x/i);

		i=j+1;

	}

	return M[x]=1-res;

}

inline ll Sphi(ll x)

{

	if(x<MAXN)return sphi[x];

	if(P.find(x)!=P.end())return P[x];

	ll res=0;

	for(register ll i=2;;)

	{

		if(i>x)break;

		ll j=x/(x/i);

		res+=1ll*(j-i+1)*Sphi(x/i);

		i=j+1;

	}

	return P[x]=1ll*(x+1)*x/2-res;

}

int main()

{

	init();read(t);

	while(t--)read(n),write(Sphi(n),' '),write(Smu(n),'\n');

	flush();

	return 0;

}