前置知識(shí)

積性函數(shù)

顧名思義，積性函數(shù)是一類(lèi)滿(mǎn)足 \(f(ab)=f(a)\times f(b)\) 的函數(shù)，當(dāng)然 \(f(ab)=f(a)\times f(b)\) 是有成立條件的，它的成立條件是 \(\gcd(a,b)=1\)。

線(xiàn)性篩

可以用 \(O(n)\) 的時(shí)間復(fù)雜度篩出積性函數(shù) \(f(x),x\in[1,n]\) 的值。既然都來(lái)學(xué)習(xí)杜教篩了，一定會(huì)線(xiàn)性篩了吧。
代碼如下：

const int N=1e7;
bool pri[N];
int prime[N],mul[N],phi[N],cnt[N],idx;
inline void sieve(int x){
    mul[1]=1;
    phi[1]=1;
    memset(pri,true,sizeof pri);
    for(int i=2;i<=x;i++){
        if(pri[i]) prime[++idx]=i,mul[i]=-1,phi[i]=i-1,cnt[i]=1;
        for(int j=1;j<=idx&&prime[j]*i<=x;j++){
            pri[i*prime[j]]=false;
            if(i%prime[j]) mul[i*prime[j]]=-mul[i],phi[i*prime[j]]=phi[i]*(prime[j]-1),cnt[i*prime[j]]=cnt[i]+1;
            else{mul[i*prime[j]]=0,phi[i*prime[j]]=phi[i]*prime[j],cnt[i*prime[j]]=cnt[i];break;}
        }
    }
}

狄利克雷卷積

存在算術(shù)函數(shù) \(f\) 和 \(g\)，其狄利克雷卷積記為 \(f*g\)，滿(mǎn)足：

或

兩種情況本質(zhì)上是一致的，只是兩種不同的寫(xiě)法。

這里給出幾對(duì)常見(jiàn)的 \(f,g\)：

1. \(\mu*I=\epsilon\) 源于 \(\sum\limits_{d|n} \mu(d)=[n=1]\)
2. \(\varphi*I=id\) 源于 \(\sum\limits_{d|n}\varphi(d)=n\)
3. \(\mu*id=\varphi\) 源于 \(\varphi(n)=\sum\limits_{i=1}^n [gcd(i,n)=1]=\sum\limits_{d|n}\frac{n}w0obha2h00\mu(d)\)
4. \(I*id=\sigma\)

其中 \(I(x)=1,\epsilon(x)=[x=1],id(x)=x\)。

整除分塊

對(duì)于 \(\lfloor \frac{n}{l}\rfloor\) 明顯存在一個(gè)區(qū)間 \([l,r]\) 使得 \(\forall i\in[l,r],\lfloor \frac{n}{i}\rfloor=\lfloor \frac{n}{l}\rfloor\)，若給定 \(l\)，\(r\) 的最大值是 \(\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor\)，如果將 \(\lfloor \frac{n}{i}\rfloor\) 值相同的 \(i\) 分為一個(gè)塊，塊的數(shù)量小于 \(2\sqrt{n}\)，可以大大優(yōu)化形似 \(\sum\limits_{i=1}^n f(i)\times g(\lfloor\frac{n}{i}\rfloor)\) 求和公式計(jì)算的時(shí)間復(fù)雜度，詳見(jiàn)例題。

杜教篩

杜教篩是一種用于求數(shù)論函數(shù)前綴和的非線(xiàn)性算法，可以在 \(O(n^{\frac{2}{3}})\) 的時(shí)間復(fù)雜度內(nèi)求出 \(S(n)=\sum\limits_{i=1}^{n} f(i)\) 的值。

為了快速求 \(f(x)\) 的前綴和，我們可以為它找到一個(gè)函數(shù) \(g(x)\) 使得 \(h(x)=(f*g)(x)\) 與 \(g(x)\) 的前綴和是好求的，這時(shí)就可以用狄利克雷卷積對(duì)式子進(jìn)行一些變換了：

其中記 \(S(x)=\sum\limits_{i=1}^{x}f(i)\)

于是我們可以得到：

根據(jù)這個(gè)式子我們可以寫(xiě)出如下偽代碼：

long long get_fsum(int x){
    long long res=sumh(x);//h的前綴和
    for(int i=2;i<=x;i=r+1){
        int r=x/(x/i);//整除分塊
        res-=(sumg(r)-sumg(i-1))*get_fsum(x/i);
    }
    return res;
}

我們假設(shè) \(g,h\) 求前綴和的時(shí)間復(fù)雜度是 \(O(1)\) 的，那么這樣的杜教篩時(shí)間復(fù)雜度是 \(O(n^{\frac{3}{4}})\) 的，證明如下：

設(shè)在 \(x\) 時(shí)我們計(jì)算 \(S(x)\) 附加計(jì)算的 \(S(y),y=\lfloor\frac{x}{i}\rfloor\ i=2,3,...,n\) 其中 \(y\) 構(gòu)成的集合為 \(T(x)=\{y|y=\lfloor\frac{x}{i}\rfloor,i=2,3,...,x\}\)，根據(jù)整除分塊的結(jié)論，我們可以得到 \(\forall z\in T(x)\) 必然有 \(T(z)\subseteq T(x)\)，我們可以記憶化記錄 \(\forall z\in T(n)\) 的 \(S(z)\) 即可，而這樣的 \(z\) 個(gè)數(shù)僅有 \(\sqrt{n}\) 個(gè)，計(jì)算 \(S(z)\) 的時(shí)間復(fù)雜度是基于整除分塊的 \(O(\sqrt{z}）\) 的，記 \(T'(n)=T(n)\cup\{n\}\)，時(shí)間復(fù)雜度即為：

我們可以將 \(T'(n)\) 拆為 \(A=\{x|x\in T'(n),x>\sqrt{n}\}\) 與 \(B=\{x|x\in T'(n),x\le\sqrt{n}\}\)

對(duì)于 \(A\) 部分：

已知 \(\sum\limits_{i=1}^{k}\sqrt{\frac{1}{i}}\sim2\sqrt{k}\)，所以：

對(duì)于 \(B\) 部分

分別帶入上下界得：

于是總時(shí)間復(fù)雜度為：

我們還可以繼續(xù)優(yōu)化杜教篩，我們先用線(xiàn)性篩篩出 \(i\le n^{\frac{2}{3}}\) 的 \(S(i)\)，此時(shí)線(xiàn)性篩與杜教篩的時(shí)間復(fù)雜度均為 \(O(n^{\frac{2}{3}})\)，達(dá)到最優(yōu)，證明過(guò)程與上面類(lèi)似。

實(shí)際應(yīng)用

接下來(lái)我們回歸題目，對(duì)于求 \(\mu\) 的前綴和就可以用前置知識(shí)中給出的 \(\mu*I=\epsilon\)，這非常容易實(shí)現(xiàn)。同理求 \(\varphi\) 的前綴和就可以用 \(\varphi*I=id\)，依舊容易實(shí)現(xiàn)，接下來(lái)給出代碼。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int t,pri[1000005],prime[1000005],idx,mul[1000005],phi[1000005];
unordered_map<int,int>mull,phii,book_mul,book_phi;
const int len=1000000;
void init(){
    mul[1]=1;
    phi[1]=1;
    memset(pri,true,sizeof pri);
    for(int i=2;i<=len;i++){
        if(pri[i]) {prime[++idx]=i;mul[i]=-1;phi[i]=i-1;}
        for(int j=1;j<=idx&&i*prime[j]<=len;j++){
            pri[i*prime[j]]=false;
            if(i%prime[j]){mul[i*prime[j]]=-mul[i];phi[i*prime[j]]=phi[i]*(prime[j]-1);}
            else{mul[i*prime[j]]=0;phi[i*prime[j]]=phi[i]*prime[j];break;}
        }
    }
    for(int i=1;i<=len;i++)mul[i]+=mul[i-1],phi[i]+=phi[i-1];
}
int get_mul(int x){
    if(x<=len)return mul[x];
    else if(book_mul[x]) return mull[x];
    int r,res=1;
    for(int i=2;i<=x;i=r+1){
        r=x/(x/i);
        res-=(r-i+1)*get_mul(x/i);
    }
    book_mul[x]=1,mull[x]=res;
    return res;
}
int get_phi(int x){
    if(x<=len)return phi[x];
    else if(book_phi[x]) return phii[x];
    int r,res=(x+1)*x/2;
    for(int i=2;i<=x;i=r+1){
        r=x/(x/i);
        res-=(r-i+1)*get_phi(x/i);
    }
    book_phi[x]=1,phii[x]=res;
    return res;
}
signed main(){
    init();
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<get_phi(n)<<" "<<get_mul(n)<<endl;
    }
    return 0;
}