杜教筛

用来求积性函数前缀积的一个算法。

给你一个 $\sum\limits_{i=1}^n f(i) $ ,让你找到 $h,g$ ,使得 $h=f*g$

$\begin{aligned}\sum\limits_{i=1}^n h(i)&=\sum\limits_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})\\&=\sum_{d=1}^ng(d)\sum_{i=1}^{n}[d\mid i]f(\frac{i}{d})\\&=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(i)\end{aligned}$

令 $S(\lfloor\frac{n}{d}\rfloor)=\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(i)$ ,

故$g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^n g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)$

即可数论分块+前缀和解决。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=5e6+5,M=5e6,mod=1e6+7;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct Hashmap
{
    struct edge{int n,next;ll w;}a[mod<<1];int len,last[mod];
    void ins(int n,ll w)
    {
        int p=n%mod;
        a[++len]=(edge){n,last[p],w};last[p]=len; 
    }
    ll qry(int n)
    {
        int p=n%mod;
        if(!last[p])return 0;
        for(int k=last[p];k;k=a[k].next)
            if(a[k].n==n)return a[k].w;
        return 0; 
    } 
}A,B;
int v[N],prime[N];
ll mu[N],phi[N];
inline void init()
{
    v[1]=mu[1]=phi[1]=1;
    int m=0;
    for(int i=2;i<=M;i++)
    {
        if(!v[i])prime[++m]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=m&&i*prime[j]<=M;++j)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0){mu[i*prime[j]]=0,phi[i*prime[j]]=phi[i]*prime[j];break;}
            mu[i*prime[j]]=-mu[i];phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
    for(int i=1;i<=M;i++)mu[i]+=mu[i-1],phi[i]+=phi[i-1];
}
I ll S_phi(int n)
{
    if(n<=M)return phi[n];
    ll w;
    if((w=A.qry(n)))
        return w;
    ll ans=0;
    for(int l=2,r;r<2147483647&&l<=n;l=r+1)
        r=n/(n/l),ans+=(r-l+1)*S_phi(n/l);
    ans=(ull)n*(n+1ll)/2ll-ans;A.ins(n,ans);
    return ans;
}
I ll S_mu(int n)
{
    if(n<=M)return mu[n];
    ll w;
    if((w=B.qry(n)))return w;
    ll ans=0;
    for(int l=2,r;r<2147483647&&l<=n;l=r+1)
        r=n/(n/l),ans+=(r-l+1)*S_mu(n/l);
    ans=1ll-ans;B.ins(n,ans);
    return ans;
}
int main()
{
    init();
    int T,n;qr(T);
    while(T--)
    {
        qr(n);
        qw(S_phi(n)),putchar(' '),qw(S_mu(n));puts("");
    }    
    return 0;
}