P4318 Powerful Number 筛做法

· · 题解

这是一篇基于 Powerful Number 筛推导的题解。

Liuhy2996 吃饭的时候口胡出来了，膜拜他/bx。

Powerful Number 筛

定义一个数 n 为 Powerful Number，当且仅当存在两个正整数，使得有 n=a^2b^3,a,b\in\mathbb{N}。
不难证明 Powerful Number 的个数是 O(\sqrt{n}) 的。

PN 筛常用于求一个积性函数 f(x) 的前缀和。我们考虑构造两个积性函数 h,g 使得有 f=g*h 成立，且满足 g(p)\equiv f(p)。
容易发现，有性质 h(p)\equiv0，现在列出前缀和的和式：

\begin{aligned} \sum_{n=0}^Nf(n)&=\sum_{n=0}^N\sum_{d|n}h(d)g\left(\frac{n}{d}\right)\\ &=\sum_{d=1}^N h(d)\sum_{n=1}^{\lfloor\frac{N}{d}\rfloor}g(n)\\ &=\sum_{d=1}^N h(d)G\left\lfloor\frac{N}{d}\right\rfloor \end{aligned}

其中，G 为 g 的前缀和。后面的 G 可以使用杜教筛筛出来，由于 h 有值的地方特别少，所以总时间复杂度为 O(n^\frac{2}{3})，瓶颈在于杜教筛。若 G 是好求的，则能做到 O(\sqrt{n}) 甚至 O(\sqrt[3]{n})。

Solution

原问题容易转换为：

\sum_{i=1}^n\mu^2(i)

构造：g(n)\equiv1，于是有：

h(p^k)= \begin{cases} 1, & k=0\\ -1, & k=2 \end{cases}

由于只有所有质因子次数为 2 时，h(n) 才有值，于是可以把题目做到 O(T\sqrt{n}\log n)，具体的，考虑求解：

\sum_{i=1}^{\sqrt{n}}h(i^2)\left\lfloor\frac{n}{i^2}\right\rfloor

整出分块一下做完了。不过还可以更优。注意到：h(n^2)=\mu(n)，于是实际上答案是：

\sum_{i=1}^{\sqrt{n}}\mu(i)\left\lfloor\frac{n}{i^2}\right\rfloor

这就做到 O(T\sqrt[3]{n}\log n) 了。

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e7+10,mod=998244353;
typedef pair<int,int> pii;
typedef long long ll;
/*

*/
int C,T=1,B=5e6;
int n,primes[N],tot,vis[N],mu[N];
int stk[N],ustk[N],sum[N];
void init(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]) primes[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*primes[j]<=n;j++){
            vis[i*primes[j]]=1;
            if(i%primes[j]==0) break;
            mu[i*primes[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
}
int Solve(int n){
    int res=0,val;
    for(int l=1,r;l<=n/l;l=r+1)
        val=n/(l*l),r=sqrt(n/val),res+=val*(sum[r]-sum[l-1]);
    return res;
}
int book[N];
void mian(){
    cin>>n;
    int l=1,r=1e10,ans=1e10;
    while(l<=r){
        int mid=(l+r)>>1;
        if(Solve(mid)>=n) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<"\n";
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>T; init(B);
    while(T--) mian();
    return 0;
}

顺带物理数学方法证明一下：

f(N)=\sum_{n=1}^{\sqrt{N}}\mu(n)\left\lfloor\frac{N}{n^2}\right\rfloor\\ \Rightarrow\lim_{N\to\infty}\frac{f(N)}{N}=\frac{6}{\pi^2}

由于 N 充分大的时候，下取整可以忽略不记，所以有：

\begin{aligned} \lim_{N\to\infty}\frac{f(N)}{N}&=\sum_{n=1}^{\infty}\frac{\mu(n)}{n^2}\\ &=\sum_{n=1}^{\infty}\prod_{p||n}\frac{1}{(1-p)^2}\\ &=\prod_p(1-p^{-2})\\ &=\zeta^{-1}(2)=\frac{6}{\pi^2} \end{aligned}

然后就做完了。