题解：AT_xmascon19_d Sum of (-1)^f(n)

· · 题解

PN 筛竟然是这么小众的筛法吗？

思路

显然 f(x) 是完全和性函数，故 (-1)^{f(x)} 是（完全）积性函数。下面设 F(x)=(-1)^{f(x)}。

可以直接 min_25，但是我不会。又懒得去推这个函数如何杜教筛。

所以考虑一些科技飞升做法，比如 PN 筛。下面会给出 PN 筛的流程，但不会有定义和证明。

首先寻找质数 p 处取值相同的积性函数 G。我们有 (-1)^{f(p)}=-1=\mu(p)，所以取 G(x)=\mu(x)。如无特殊说明，下面 p 均为质数。

然后设积性函数 H(x) 满足 F=G*H，这里 * 是狄利克雷卷积，则 H 只在 PN 处不为 0。

则我们有 F(p^k)=\sum\limits_{i=0}^k \mu(p^i)H(p^{k-i})。简单化简得到 (-1)^k=H(p^k)-H(p^{k-1})。结合 H(p)=0，有 H(p^k)=[2|k]。

我们有 \sum\limits_{i=1}^n F(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}H(d)\mu(\dfrac{i}{d})。

枚举因数变枚举倍数得到 \sum\limits_{i=1}^n F(i)=\sum\limits_{d=1}^n\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)H(d)。

设 S(x)=\sum\limits_{i=1}^x\mu(i)，化简得到 \sum\limits_{i=1}^n F(i)=\sum\limits_{d=1}^n H(d)S(\lfloor\dfrac{n}{d}\rfloor)。

枚举令 H(d)\neq 0 的 O(\sqrt n) 个 PN，用一次杜教筛算出 O(\sqrt n) 个本质不同的 S(\lfloor\dfrac{n}{d}\rfloor) 即可。

瓶颈在于一次杜教筛，时间复杂度 O(n^{\frac 2 3})。

代码

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MAXN=5e7+1,LIM=1e6+1;
bool vis[MAXN];
ll mu[MAXN];
int pr[3001135],cnt;
inline void init(){
    mu[1]=1;
    F(i,2,MAXN-1){
        if(!vis[i]) pr[++cnt]=i,mu[i]=-1;
        F(j,1,cnt){
            ll k=i*pr[j];
            if(k>=MAXN) break;
            vis[k]=1;
            if(i%pr[j]) mu[k]=-mu[i];
            else break;
        }
    }
    F(i,2,MAXN-1) mu[i]+=mu[i-1];
    return;
}
__gnu_pbds::gp_hash_table<ll,int>res;
ll n,ans;
ll S(ll x){
    if(x<MAXN&&x!=n) return mu[x];
    if(res.find(x)!=res.end()) return res[x];
    ll ans=1;
    for(ll l=2,r;l<=x;l=r+1){
        ll qwq=x/l;
        r=x/qwq;
        ans=ans-(r-l+1)*S(qwq);
    }
    return res[x]=ans;
}
void dfs(int step,ll now,ll H){
    ll pri=pr[step],nxt=pri*pri;
    if(step>cnt||now>n/nxt){
        ans+=H*S(n/now);
        return;
    }
    dfs(step+1,now,H);
    for(int expo(2);now*nxt<=n;++expo,nxt*=pri) dfs(step+1,now*nxt,H*((expo&1)==0));
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    init(),S(n);
    dfs(1,1,1);
    cout<<ans;
    return 0;
}