杜教筛是用来求一类积性函数的前缀和，利用数论分块的思想来降低复杂度

假设我们现在要求 \(S(n) = \sum_{i = 1}^n f(i)\) ，\(f(i)\) 为积性函数, \(n \leqslant 10^{12}\) ，假设有另一个积性函数 \(g\)。我们来求它们狄利克雷卷积的前缀和
\[ \begin{align} &\sum_{i = 1}^n (g * f) = \sum_{i = 1}^n \sum_{d \mid i} g(d) f(\frac{i}{d}) \\ =& \sum_{d = 1}^n g(d) \sum_{d|i} f(\frac{i}{d}) \\ =& \sum_{d = 1}^n g(d) \sum_{i = 1}^{\frac{n}{d}}f(i) \\ =& \sum_{d = 1}^n g(d) S(\frac{n}{d}) \end{align} \]
容斥处理一下，得到
\[ g(1)S(n) = \sum_{d = 1}^n g(d)S(\frac{n}{d}) - \sum_{d = 2}^n g(d)S(\frac{n}{d}) \]
至于 \(g\) 的选择，需要看具体情况

原函数 \(f(n)\)	选取的函数 \(g(n)\)	递归式
\(\mu(n)\)	\(1\)	\(S(n) = 1 - \sum_{d = 2}^n S(\frac{n}{d})\)
\(\varphi(n)\)	\(1\)	\(S(n) = \frac{n (n + 1)}{2} - \sum_{d = 2}^n S(\frac{n}{d})\)
\(n\cdot \varphi(n)\)		\(S(n)=\sum_{i=1}^{n}i^2-\sum_{d=2}^{n}d\cdot S(\lfloor\frac{n}{d}\rfloor)\)

注意询问数量较多时可以采用 unordered_map 做记忆化来加速。

卡常什么的太讨厌了

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 7.5e6+5;
map<signed,int> mp,mm;
bool isNotPrime[N + 5];
int mu[N + 5], phi[N + 5];
signed primes[N + 5], cnt;
inline void euler() {
    isNotPrime[0] = isNotPrime[1] = true;
    mu[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!isNotPrime[i]) {
            primes[++cnt] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt; j++) {
            int t = i * primes[j];
            if (t > N) break;
            isNotPrime[t] = true;
            if (i % primes[j] == 0) {
                mu[t] = 0;
                phi[t] = phi[i] * primes[j];
                break;
            } else {
                mu[t] = -mu[i];
                phi[t] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

int Mu(int n) {
    if(n<=N) return mu[n];
    if(mm[n]) return mm[n];
    register signed l=2,r;
    int ans=1;
    while(l<=n) {
        r=n/(n/l);
        ans-=(r-l+1)*Mu(n/l);
        l=r+1;
    }
    mm[n]=ans;
    return ans;
}

int Phi(int n) {
    if(n<=N) return phi[n];
    if(mp[n]) return mp[n];
    register signed l=2,r;
    int ans=n*(n+1)/2;
    while(l<=n) {
        r=n/(n/l);
        ans-=(r-l+1)*Phi(n/l);
        l=r+1;
    }
    mp[n]=ans;
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    euler();
    for(int i=1;i<=N;i++) mu[i]+=mu[i-1], phi[i]+=phi[i-1];
    int n,t;
    cin>>n;
    while(n--) {
        cin>>t;
        cout<<Phi(t)<<" "<<Mu(t)<<endl;
    }
}