发布时间：2025-05-22

杜教筛

在$n^{\frac{2}{3}}$的时间内求解$S(n)=\sum_{i=1}^nf(i)$

构造一个函数g使得：

1. 可以快速计算$\sum_{i=1}^n(f*g)(i)$
2. 可以快速计算g的前缀和，可以用数论分块快速计算$\sum_{i=2}^ng(i)S(\lfloor \frac{n}{i} \rfloor)$

递推式：

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

求莫比乌斯函数前缀和和欧拉函数前缀和

莫比乌斯函数：

$\epsilon=[n=1],\epsilon=\mu * 1$

$S(n)=1-\sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)$

欧拉函数：

$id(x)=x,\phi *1=id$

$S(n)=\frac{n(n+1)}{2}-\sum_{i=2}^nS(\lfloor \frac{n}{i} \rfloor)$

vector<int> mu,sum_mu,phi,sum_phi;
vector<int> prime;
vector<bool> st;
void sieve(int n){
    mu.resize(n+1);
    sum_mu.resize(n+1);
    phi.resize(n+1);
    sum_phi.resize(n+1);
    st.resize(n+1);
    mu[1]=1;
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime.push_back(i);
            mu[i]=-1;
            phi[i]=i-1;
        }
        for(auto p:prime){
            if(p*i>n)break;
            st[p*i]=1;
            if(i%p==0){
                mu[p*i]=0;
                phi[p*i]=phi[i]*p;
                break;
            }
            else{
                mu[p*i]=-mu[i];
                phi[p*i]=phi[i]*(p-1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        sum_mu[i]=sum_mu[i-1]+mu[i];
        sum_phi[i]=sum_phi[i-1]+phi[i];
    }
}
unordered_map<int,int> mp_mu,mp_phi;
int S_mu(int x){
    if(x<mu.size())return sum_mu[x];
    if(mp_mu.count(x))return mp_mu[x];
    int res=1;
    for(int l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        res-=S_mu(x/l)*(r-l+1);
    }
    return mp_mu[x]=res;
}
int S_phi(int x){
    if(x<phi.size())return sum_phi[x];
    if(mp_phi.count(x))return mp_phi[x];
    int res=x*(x+1)/2;
    for(int l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        res-=S_phi(x/l)*(r-l+1);
    }
    return mp_phi[x]=res;
}
void solve(){
    int n;
    cin>>n;
    cout<<S_phi(n)<<" "<<S_mu(n)<<"\n";
}

$f(i)=i^2\phi(i)$

$f=id^2\phi$，构造$g=id^2$

$(f*g)(i)=\sum_{d|i}f(d)g(\frac{i}{d})=\sum_{d|i}d^2\phi(d)\frac{i^2}{d^2}=i^2 \sum_{d|i}\phi(d)=i^3$

$S(n)=(\frac{n(n+1)}{2})^2-\sum_{i=2}^n i^2S(\lfloor \frac{n}{i} \rfloor)$