杜教筛--求积性函数前缀和

博主链接

模版中以求欧拉函数和莫比乌斯函数前缀和为例

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int;
#define N 2001000
#define ni 500000004  //2的逆元
using namespace std;
const long long int mod=0x3f3f3f3f3f3f3f;
inline void read(long long &x)  //输入外挂 
{
    x=0;
    static int p;p=1;
    static char c;c=getchar();
    while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
    x*=p;
}
bool vis[N];
int mu[N],sum1[N];
long long phi[N],sum2[N];
int cnt,prim[N];
int e,e1;
map<long long ,int>w,w1;  //哈希 w用来求phi前缀和  w1用来求miu前缀和 
void get(int maxn)
{
    phi[1]=mu[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(!vis[i])
        {
            prim[++cnt]=i;
            mu[i]=-1;phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&prim[j]*i<=maxn;j++)
        {
            vis[i*prim[j]]=1;
            if(i%prim[j]==0)
            {
                phi[i*prim[j]]=phi[i]*prim[j];
                break;
            }
            else mu[i*prim[j]]=-mu[i],phi[i*prim[j]]=phi[i]*(prim[j]-1);
        }
    }
    for(int i=1;i<=maxn;i++)sum1[i]=sum1[i-1]+mu[i],sum2[i]=(sum2[i-1]+phi[i])%mod;   //打一个maxn的phi前缀和表 和miu前缀和表  
}
int djsmu(long long x)	//	求miu前缀和 
{
    if(x<=2000000)return sum1[x];
    if(w.count(x))return w[x];
    int ans=1;
    for(long long l=2,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        ans-=(r-l+1ll)*djsmu(x/l);
    }
    return w[x]=ans;
}
long long djsphi(long long x)	//求phi 前缀和 
{
    if(x<=2000000)return sum2[x];
    if(w1.count(x))return w1[x];
    long long ans=(x %mod* ((x + 1) % mod)) % mod*ni%mod;
    for(long long l=2,r;l<=x;l=r+1)
    {
        r=x/(x/l);  //最后一个分块中的数
        ans = (ans - ((r - l + 1) % mod*djsphi(x / l)) % mod + mod) % mod;
    }
    return w1[x]=ans;
}
int main()
{
    long long t;
    read(t);
    get(2000000);
    while(t--){
        static long long n;
        read(n);
        printf("%lld %d\n",djsphi(n),djsmu(n));
    }
    return 0;
}