這是一種對于一個數論函數 \(f(n)\)，計算 \(S(n)=\sum_{i=1}^n f(i)\) 的快速方法。

構造兩個積性函數 \(h,g\) 滿足 \(h=g*f\)，根據卷積的定義，有 \(h(i)=\sum_{d|i}g(d)f(\frac{i}w0obha2h00)\)，對 \(h\) 求和，有：

然后我們得到

記憶化之后復雜度是 \(O(n^{\frac{3}{4}})\) 的捏。

如果預處理 \(S(1,...,k)\)，那么復雜度 \(O(k)+O(\frac{n}{\sqrt k})\) 的捏。

當 \(k=n^{\frac{2}{3}}\) 時候有最小值 \(O(n^{\frac{2}{3}})\) 的捏。

歐拉函數怎么獨角骰？歐拉函數怎么獨角骰？歐拉函數怎么獨角骰？

首先有一個 \(n=\sum_{d|n}\phi(d)\)，然后套用上面的柿子 \(g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{i=2}^n g(i)S(?\frac{n}{i}?)\) 可得：

梅比烏斯怎么獨角曬？梅比烏斯怎么獨角曬？梅比烏斯怎么獨角曬？

首先有一個 \([n=1]=\sum_{d|n}\mu(d)\)，還是套用上面的柿子可得：

小技巧。

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=5000010;

int t, n, k=5e6;
int vis[N], p[N], top, phi[N], mu[N];
map<int,int> sphi, smu;

void init() {
	vis[0]=vis[1]=phi[1]=mu[1]=1;
	up(i,2,k) {
		if(!vis[i]) p[++top]=i, phi[i]=i-1, mu[i]=-1;
		for(int j=1; j<=top&&i*p[j]<=k; ++j) {
			int x=i*p[j]; vis[x]=1;
			if(i%p[j]) mu[x]=-mu[i], phi[x]=phi[i]*(p[j]-1);
			else { mu[x]=0, phi[x]=phi[i]*p[j]; break; } 
		}
	}
	up(i,1,k) phi[i]+=phi[i-1], mu[i]+=mu[i-1];
}

int getphi(int x) {
	if(x<=k) return phi[x];
	if(sphi.find(x)!=sphi.end()) return sphi[x];
	int res=(1+x)*x/2;
	for(int l=2, r; l<=x; l=r+1) {
		r=min(x,x/(x/l));
		res-=(r-l+1)*getphi(x/l);
	}
	return sphi[x]=res;
}

int getmu(int x) {
	if(x<=k) return mu[x];
	if(smu.find(x)!=smu.end()) return smu[x];
	int res=1;
	for(int l=2, r; l<=x; l=r+1) {
		r=min(x,x/(x/l));
		res-=(r-l+1)*getmu(x/l); 
	}
	return smu[x]=res;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	init(), cin >> t;
	while(t--) {
		cin >> n;
		cout << getphi(n) << ' ' << getmu(n) << '\n';
	}
	return 0;
}