用途
求积性函数 \(f\) 的前缀和 \(F(n)=\sum_n^{i=1} f(i)\).
复杂度 \(O(\sqrt{n})\) 或 \(O(\sqrt{n}\log n)\) 或 \(O(n^{\frac{2}{3}})\).
使用条件
存在一个函数 \(g\) 满足：
- \(g\) 是积性函数
- \(g\) 易求前缀和
- 对于质数 \(p\)，\(g(p)=f(p)\)
Powerful Number
定义为每个质因子次数都不小于 \(2\) 的数.
将 PN 表示为 \(a^2b^3\) 的形式, 积分可以证明, \(n\) 以内的 PN 只有 \(O(\sqrt{n})\) 个.
可以通过线性筛筛出 \(\sqrt{n}\) 内的所有质数, 然后直接 dfs 质数指数搜出所有 PN, 复杂度是 \(O(\sqrt{n})\) 的.
原理
首先，构造出合适的 \(g\), 记 \(G(n)=\sum^n_{i=1} g(i)\).
然后考虑另一个函数 \(h\), 满足 \(f=g∗h\), 故 \(h\) 也为积性函数.
代入 \(f(p)=h(p)g(1)+g(p)h(1)=h(p)+g(p)\) 容易得到 \(h(p)=0\) , 由于 \(h\) 为积性函数, 故 \(h\) 仅在 PN 处不为 \(0\).
\[F(n) = \sum_{i=1}^{n} f(i) = \sum_{i=1}^{n} \sum_{d|i}h(i)g(\frac{i}{d})\\ = \sum_{d=1}^{n} h(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} g(i)\\ = \sum_{d~is~PN}^{n} h(d) G(\lfloor \frac{n}{d} \rfloor) \]搜索所有 PN, 维护出 \(h(d)\) 即可计算, 因此需要求出 \(h(p^c)\) 的值, 共 \(O(\Pi(\sqrt{n})*\log{n}) = O(\sqrt{n})\) 个.
若能线性预处理 \(h(p^c)\) , 则总复杂度为 \(O(\sqrt{n})\).
若能快速求 \(f(p^c)\) 和 \(g(p^c)\), 则可以根据 \(h(p^c)=f(p^c)-\sum_{i=1}^{c} g(p^i)h(p^{c-i})\), \(O(\sqrt{n}\log{n})\) 预处理.
- 常见 \(\frac{g(p^c)}{g(p^{c-1})}\) 为常数 \(t\) 时, 易得:
- 则 \(h(p^c)=f(p^c)-t * f(p^{c-1})\).
若使用杜教筛求 \(G\), 则总复杂度和杜教筛相同.
因为若事先计算一次 \(G(n)\) , 则杜教筛过程中用到的 \(G(\lfloor \frac{n}{d} \rfloor)\) 都是访问过的.
例题
\(f(p^c)=\frac{p^c}{c}\)
令 \(g(x)=x\), 可求出 \(h(p^c)=-\frac{p^c}{c(c-1)}\), 即可筛出 \(F(n)\).
// 求 g(x) 前缀和
inline ll gsum(ll x){
return (__int128)x*(x+1)/2%p;
}
// 预处理 h(p^c)
vector<ll>H[N];
inline void get_h(ll n){
for(int i=1;i<=tot;++i){
__int128 prod=(ll)pri[i]*pri[i];
int cnt=2;
H[i].resize(2);
while(prod<=n){
H[i].push_back(sub(0,mul(mul(prod,inv[cnt]),inv[cnt-1])));
prod*=pri[i];
++cnt;
}
}
}
ll ans;
// 搜索所有 PN, 同时维护 h(x), 统计答案
inline void dfs(int id,ll prod,ll h,ll n){
ll t=pri[id];
if(id>tot||(__int128)prod*t*t>n){
ans=add(ans,mul(h,gsum(n/prod)));
return ;
}
dfs(id+1,prod,h,n);
prod*=t;
int c=1;
while((__int128)prod*t<=n){
++c;
prod*=t;
dfs(id+1,prod,mul(h,H[id][c]),n);
}
}
inline ll Powerful_Number_Sieve(ll n){
ans=0;
inv[1]=1;
for(int i=2;i<=64;++i){
inv[i]=mul((p-p/i),inv[p%i]);
}
get_prime(sqrtl(n)); // 筛质数
get_h(n);
dfs(1,1,1,n);
}