以前学了些，后来也没用过，就搁置了，不会了，重新捡起来。决定写下来。参考罗老师的博客。
杜教筛 以及积性函数的前世今生 --算法竞赛专题解析（4）罗勇军的博客-CSDN博客积性函数在竞赛中
也可以参考唐老师的博客
浅谈一类积性函数的前缀和
杜教筛的核心
用途：
用于低于线性时间里，高效率求一些积性函数的前缀和
算法：
说简单点就是整除分块+狄利克雷卷积+线性筛
公式：
$g(1)S(n)=\sum{i=1}^nh(i)-\sum{i=2}^ng(i)S([\frac{n}{i}])$
时间复杂度会缩小到$O(n^{\frac{2}{3}})$
积性函数
如果p和q互质并且$f(pq)=f(p)*f(q)$则称f是积性函数
如果对任意p和q都有$f(pq)=f(p)*f(q)$则成f是完全积性函数
常见的积性函数
除数函数 $\sigmak(n)=\sum {d|n} d^k$,表示n的约数的k次幂和，注意$\sigma _{k}(n)$与 $\sigma ^k(n)$是不同的 。
约数个数函数$\tau(n)=\sigma0(n) = \sum{d|n}$表示n的约数个数，一般也形成d(n)。
约数和函数$\sigma(n)=\sigma1(n)=\sum{d|n}d$,表示n的约数和。
欧拉函数$\varphi(n)=\sum{i=1}^n[(n,i)=1]\times1$表示不大于n切与n沪指的正整数个数，另外$\sum{i=1}^{n}[(n,i)=1]i=\frac{n\varphi(n)+[n=1]}{2}$且对于正整数n>2来说$\varphi(n)$是偶数。
莫比乌斯函数$\mu(n)$，在狄利克雷卷积的惩罚中与恒等函数互为逆元。$\mu(1)=1,$对于无平方的因子数，$n=\prod^t_{i=1}p_i$有$\mu(n)=(-1)^t$,对于有平方因子数有$\mu(n)=0$.
元函数$e(n)=[n=1]$，狄利克雷卷积的乘法单位元，完全积性
恒等函数$I(n)=1$完全积性
单位函数$id(n)=n$，完全积性
幂函数$id^k(n)=n^k,$完全积性
两个重要定理：
$[n=1]=\sum_{d|n}\mu(d)$
$n=\sum_{d|n}\varphi(d)$
整除分块：
自己以前写的：
https://blog.csdn.net/weixin_45911397/article/details/107870837
狄利克雷卷积
$(fg)(n)=h(n)$且f(n)和g(n)都是积性函数，那么$(fg)(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$满足，交换律结合律，加法分配率
莫比乌斯反演：
自已以前写的：
https://blog.csdn.net/weixin_45911397/article/details/106079611
杜教筛
公式：
$g(1)S(n)=\sum{i=1}^{n}h(i)-\sum{i=2}^{n}g(i)s([\frac{n}{i}])$
推一个具体的式子：
$\sum_{i=1}^{n}\phi(i)$
这里我们就要使用性质了：$n=\sum_{d|n}\phi(d)$
$n=\phi(n)+\sum_{d|n ,d<n}\phi(d)$
$\phi(n)=n-\sum_{d|n,d<n}\phi(d)$
$\sum{i=1}^n\phi(i)=\sum{i=1}^n(i-\sum_{d|n,d<n}\phi(d))$
$\sum{i=1}^n\phi(i)=\frac{n*(n+1)}{2}-
\sum{i=1}^n\sum_{d|n,d<n}\phi(d)$
枚举$\frac{i}{d}=d'$
$\sum{i=1}^n\phi(i)=\frac{n*(n+1)}{2}-
\sum{d'=2}^{d'<=n}\sum_{d=1}^{d<=[\frac{n}{d'}]}\phi(d)$
令$S(n)=\sum_{i=1}^n\phi(i)$
$S(n)=\frac{n*(n+1)}{2}-\sum_{i=2}^nS(\frac{n}{i})$
//代码改写自：https://blog.csdn.net/KIKO_caoyue/article/details/100061406
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e6+7; //超过n^(2/3)，够大了
int prime[maxn]; //记录质数
bool vis[maxn]; //记录是否被筛；
int mu[maxn]; //莫比乌斯函数值
ll phi[maxn]; //欧拉函数值
unordered_map<int,int> summu; //莫比乌斯函数前缀和
unordered_map<int,ll> sumphi; //欧拉函数前缀和
void init(){
//线性筛预计算一部分答案
int cnt = 0;
vis[0] = vis[1] = 1;
mu[1] = phi[1] = 1;
for(int i=2;i<maxn;i++){
if(!vis[i]){
prime[cnt++] = i;
mu[i] = -1;
phi[i] = i-1;
}
for(int j=0;j<cnt && i*prime[j]<maxn;j++){
vis[i*prime[j]] = 1;
if(i%prime[j]){
mu[i*prime[j]] = -mu[i];
phi[i*prime[j]] = phi[i]*phi[prime[j]];
}
else{
mu[i*prime[j]] = 0;
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
}
}
for(int i=1;i<maxn;i++){
//最后，mu[]和phi[]改为记录1~maxn的前缀和。
mu[i] += mu[i-1];
phi[i] += phi[i-1];
}
}
int gsum(int x){
// g(i)的前缀和
return x;
}
ll getsmu(int x){
if(x < maxn) return mu[x]; //预计算
if(summu[x]) return summu[x]; //记忆化
ll ans = 1; //杜教筛公式中的 1
for(ll l=2,r;l<=x;l=r+1){
//用整除分块计算杜教筛公式
r = x/(x/l);
ans -= (gsum(r)-gsum(l-1))*getsmu(x/l);
}
return summu[x] = ans/gsum(1);
}
ll getsphi(int x){
if(x < maxn) return phi[x];
if(sumphi[x]) return sumphi[x]; //记忆化，每个sumphi[x]只用算一次
ll ans = x*((ll)x+1)/2; //杜教筛公式中的 n(n+1)/2
for(ll l=2,r;l<=x;l=r+1){
//用整除分块计算杜教筛公式，这里算 sqrt(x)次
r = x/(x/l);
ans -= (gsum(r)-gsum(l-1))*getsphi(x/l);
}
return sumphi[x] = ans/gsum(1);
}
int main(){
init(); //用线性筛预计算一部分
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
printf("%lld %lld\n",getsphi(n),getsmu(n));
}
return 0;
}
