杜教筛

解决问题：已知\(f(i)\)是积性函数，求\(\sum\limits_{i=1}^nf(i)\)。

设\(S(n)=\sum\limits_{i=1}^nf(i)\)

再找一个积性函数\(g()\)，求\(f*g\)的前缀和：
\(\sum\limits_{i=1}^{n}(f*g)(i)\)
\(=\sum\limits_{i=1}^{n}\sum\limits_{d|i}f(d)*g(\frac{i}{d})\)
\(=\sum\limits_{d=1}^{n}g(d)\sum\limits_{i=1}^{\frac{n}{d}}f(i)\)
\(=\sum\limits_{d=1}^{n}g(d)*S(\frac{n}{d})\)

考虑\(g(1)S(n)\)：
\(g(1)S(n)\)
\(=\sum\limits_{i=1}^{n}g(i)*S(\frac{n}{i})-\sum\limits_{i=2}^{n}g(i)*S(\frac{n}{i})\)
\(=\sum\limits_{i=1}^{n}(f*g)(i)-\sum\limits_{i=2}^{n}g(i)*S(\frac{n}{i})\)

发现只要找到一个合适的积性函数\(g\)满足可以快速求\(f*g\)和\(g\)的前缀和，那么就可以结合除法分块递归求解\(\sum\limits_{i=1}^{n}f(i)\)。

复杂度为\(O(n^{\frac{3}{4}})\)

优化：
1.线性筛前\(n^{\frac{2}{3}}\)个答案，复杂度为\(O(n^{\frac{2}{3}})\)
2.中途用哈希表记录答案。

例子：
1.求\(\sum\limits_{i=1}^{n}\varphi(i)\)

由\((\varphi*1=id)\)，令\(f=\varphi,g=1,f*g=id\)

2.求\(\sum\limits_{i=1}^{n}\mu(i)\)

由\(\mu*1=\epsilon\)，令\(f=\mu,g=1,f*g=\epsilon\)。

模板题
code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5000010;
int T,n;
int mu[maxn],sum2[maxn],phi[maxn];
ll sum1[maxn];
bool vis[maxn];
vector<int>prime;
unordered_map<int,ll>mp1;
unordered_map<int,int>mp2;
inline void pre_work(int n)
{
    vis[1]=1;mu[1]=phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])prime.push_back(i),mu[i]=-1,phi[i]=i-1;
        for(unsigned int j=0;j<prime.size()&&1ll*i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++)sum1[i]=sum1[i-1]+phi[i],sum2[i]=sum2[i-1]+mu[i];
}
inline ll getphi(ll n)
{
    if(n<=5000000)return sum1[n];
    if(mp1.count(n))return mp1[n];
    ll res=1ll*n*(n+1)/2;
    for(ll l=2,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        res-=1ll*(r-l+1)*getphi(n/l);
    }
    return mp1[n]=res;
}
inline int getmu(int n)
{
    if(n<=5000000)return sum2[n];
    if(mp2.count(n))return mp2[n];
    int res=1;
    for(int l=2,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        res-=(r-l+1)*getmu(n/l);
    }
    return mp2[n]=res;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    pre_work(5000000);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%lld %d\n",getphi(n),getmu(n));
    }
    return 0;
}