开坑终于开到这里了,先庆贺一下。
前置知识 ： 狄利克雷克雷卷积与数论函数。
可见 莫比乌斯反演与数论函数 （附 ： 文章比较古老，可能过时）
符号约定:
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
{\mathscr P}\!art\ 1 : 杜教筛
一般化推导
-
从卷积开始
杜教筛用于求数论函数的前缀和，利用的是迪利克雷卷积的性质。
假设我们有一个狄利克雷卷积式子 A*B=C。欲求 S_A(N)。
( 注意大写 N 和小写 n 的区别 )
写出 S_C(n)=\sum\limits_{i=1}^nC(i)
=\sum\limits_{i=1}^n\sum\limits_{d|i}B(d)A(i/d)
=\sum\limits_{d=1}^nB(d)\sum\limits_{d|i}^{n}A(i/d)
=\sum\limits_{d=1}^nB(d)\sum\limits_{i=1}^{\lfloor n/d\rfloor}A(i)
=\sum\limits_{d=1}^nB(d)S_A(\lfloor n/d\rfloor)
将 S_A(n) 移项（注意 B(1)=1），整理得 ：
S_A(n)=S_C(n)-\sum\limits_{d=2}^nB(d)S_A(\lfloor n/d\rfloor)
怎么快速计算这个式子呢？
-
优化&复杂度分析
这是个递归式，先假设我们已知右侧的所有量（可以 O(1) 任意取用），只考虑求和的复杂度。
可以使用整除分块，求解一次的复杂度为 O(\sqrt{n})。
考虑问题中涉及到的本质不同的 S_A(n) 有多少个。
- 整除定理① ： \big\lfloor\lfloor n/a\rfloor/b\big\rfloor=\lfloor n/(ab)\rfloor
推论 ： N 无论经历多少次整除，所得均 \in \big\{\lfloor N/k\rfloor \big\}。
-
整除定理② ： \big\{r\Big|\lfloor n/r\rfloor≠\lfloor n/(r-1)\rfloor\big\}=\big\{\lfloor n/k\rfloor\big\}
人话 ： 整除分块中的边界恰是由 \lfloor n/k\rfloor 产生的。
证明 ： 考虑 r=\big\lfloor n/\lfloor n/r\rfloor\big\rfloor。
（这两个定理是学习筛法的重要基础）
取 $\lfloor N/i\rfloor$ 中最大的 $\sqrt{N}$ 个对整除分块的复杂度求和。
复杂度为 $O\bigg(\sum\limits_{i=1}^{\sqrt{N}}\sqrt{N/i}\bigg)=O(N^{3/4})$ （需要积分）
这个复杂度还不够好，考虑使用线性筛预处理 $T$ 以内的 $S(n)$。
这样，若 $N/i\leq T$ 的就不需要求了，可以推出 $i<N/T$ 才对复杂度有贡献。
复杂度为 $O\bigg(T+\sum\limits_{i=1}^{N/T}\sqrt{N/i}\bigg)=O(T+nT^{-1/2})$。
令 $T=nT^{-1/2}$ 解得 $T=n^{2/3}$ 可得最优复杂度为 $O(n^{2/3})$。
-
原料
接下来，解决 B,C 函数的求值问题。
$C$ 函数的参数和 $A$ 函数的参数是对应的，也只需要 $\big\{\lfloor N/k\rfloor \big\}$ 处的值。
给出一个数论函数 $F$ ,对于给定的 $n$ 和任意 $d$ ,求出 $S_F(\lfloor n/d\rfloor)$ ,称为**块筛**。
显然，只需要对 $B,C$ 完成块筛，即可满足需求。
-
适用性
假如 F 能在 O(n^{2/3}) 内完成块筛,则称之为可杜教筛。
不难得出，在 A*B=C 这一卷积式中，如果 B,C 都可可杜教筛, A可线筛（存在较为普适的积性函数筛法）,那么 A 也可杜教筛。
此外，已知 A,B 得到 C 也是容易的。式子如下：
S_C(n)=\sum\limits_{d=1}^nB(d)S_A(\lfloor n/d\rfloor)
于是，在任意卷积式子中都可以“知二筛一”了。
由此可以发现，杜教筛在经典的知识体系里面是很好用的。
一些具体函数的筛法
常见的数论函数 : 如 \mu,\varphi ，直接求前缀和并没有什么思路，但这些函数都满足一些优美的卷积恒等式。
某种程度上，卷积式也可以看作对函数定义的刻画。
如 \mu*I=e,\ \ \varphi*I=id ,而 I,e,id 都是完全积性函数,其前缀和易求。
卷积式 ： \mu*I=e。
套用式子得 S_{\mu}(n)=S_{e}(n)-\sum\limits_{i=2}^nI(i)S_{\mu}(\lfloor n/i\rfloor)
即 S_{\mu}(n)=1-\sum\limits_{i=2}^nS_{\mu}(\lfloor n/i\rfloor)
卷积式 ： \varphi*I=id。
套用式子得 S_{\varphi}(n)=S_{id}(n)-\sum\limits_{i=2}^nI(i)S_{\varphi}(\lfloor n/i\rfloor)
即 S_{\mu}(n)=\frac{n(n+1)}{2}-\sum\limits_{i=2}^nS_{\varphi}(\lfloor n/i\rfloor)
记忆化可以不使用 map，记录 \lfloor n/d\rfloor 中的 d 即可。
两个函数一起递归可以减小整初分块的常数。
由于询问较多，预处理略多一些。
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define Limit 6000500
using namespace std;
bool e[Limit];
int tn,lim,p[Limit];
ll phi[Limit],mu[Limit];
void getsth()
{
e[1]=1;phi[1]=mu[1]=1;
for (int i=2,t;i<=lim;i++){
if (!e[i]){
p[++tn]=i;
mu[i]=-1;
phi[i]=i-1;
}
for (int j=1;j<=tn&&(t=p[j]*i)<=lim;j++){
e[t]=1;
if (i%p[j]==0){
phi[t]=phi[i]*p[j];
break;
}mu[t]=-mu[i];
phi[t]=phi[i]*(p[j]-1);
}
}
for (int i=2;i<=lim;i++){
mu[i]+=mu[i-1];
phi[i]+=phi[i-1];
}
}
int N;
ll _Smu[2005],_Sphi[2005];
inline ll Smu(int n)
{
if (n<=lim)return mu[n];
return _Smu[N/n];
}
inline ll Sphi(int n)
{
if (n<=lim)return phi[n];
return _Sphi[N/n];
}
void S(int n,int d)
{
if (n<=lim||_Sphi[d])return ;
ll tmu=1,tphi=1ll*n*(n+1)>>1;
int l=2,r;
for (;l<=n;){
r=n/(n/l);
S(n/l,d*l);
tmu-=Smu(n/l)*(r-l+1);
tphi-=Sphi(n/l)*(r-l+1);
l=r+1;
}_Smu[d]=tmu;_Sphi[d]=tphi;
}
int Sn[15];ll Tn;
int main()
{
int T;scanf("%d",&T);
for (int i=1;i<=T;i++){
scanf("%d",&Sn[i]);
Tn+=Sn[i];
}lim=min((int)pow(Tn,0.66)+5,6000000);
getsth();
for (int i=1;i<=T;i++){
N=Sn[i];
memset(_Sphi,0,sizeof(_Sphi));
S(N,1);
printf("%lld %lld\n",Sphi(N),Smu(N));
}return 0;
}
定义 ： σ_k(n)=\sum\limits_{d|n}d^k ，即因数的 k 次方和。
易得 σ_k=I*id_k。
套用式子得 \sum\limits_{i=1}^nσ_k(i)=\sum\limits_{i=1}^nid_k(i)S_I(\lfloor n/i\rfloor)。
即 \sum\limits_{i=1}^nσ_k(i)=\sum\limits_{i=1}^ni^k\lfloor n/i\rfloor
整除分块求解， i^k 的部分和是经典的自然数幂和问题。
直接整除分块复杂度仍然是 O(n^{3/4}) ，同样需要线筛预处理才能做到 O(n^{2/3})。
- 例题③ : \mu·id_k，\varphi·id_k (点乘)
剥点乘有一个技巧,当 C 是完全积性函数时 (A·C)*(B·C)=(A*B)·C (提公因式)
证明 : \sum\limits_{d|n}\big(A(d)C(d)\big)\big(B(\frac{n}{d})C(\frac{n}{d})\big)=C(n)\sum\limits_{d|n}A(d)B(\frac{n}{d})
这里卷上id_k得到 :
(\mu·id_k)*id_k=(\mu·id_k)*(I·id_k)=(\mu*I)·id_k=e
(\varphi·id_k)*id_k=(\varphi·id_k)*(I·id_k)=(\varphi*I)·id_k=id_{k+1}
得到卷积式后杜教筛就是体力活了。
从上述推导中可以看出，从点乘里面剥完全积性函数相对容易。
卷上 id 得到 :
\mu^2*\big((\mu·id)*id\big)=\mu^2*\big((\mu*I)·id\big)=\mu^2*e=\mu^2
- **例题⑤** : $\mu^2·id_k
似乎和杜教筛关系不大了……
回忆 ： \mu^2(n)=\sum\limits_{d^2|n}\mu(d)。
{\rm Ans}=\sum\limits_{i=1}^n\mu^2(i)*i^k
=\sum\limits_{i=1}^ni^k\sum\limits_{d^2|n}\mu(d)
=\sum\limits_{d=1}^{\sqrt{n}}\mu(d)\sum\limits_{d^2|i}^ni^k
=\sum\limits_{d=1}^{\sqrt{n}}\mu(d)d^{2k}\sum\limits_{i=1}^{\lfloor n/d^2\rfloor}i^k
后半部分都是自然数幂和能够解决的。根据 \lfloor n/d^2\rfloor 分块。
复杂度和 \mu^2 相同，求单个 O(n^{1/3}) ,求块筛 O(n^{3/5})。
{\mathscr P}\!art\ 2 : 贝尔级数
定义
对于积性函数 f(n) ,定义其在质数 p 意义下的贝尔级数为:
F_p(x)=\sum\limits_{i=0}^{\infty}f(p^i)x^i
即在质数 p 及其幂次处观察这个积性函数。
由于相乘转化为了指数相加，所以这个东西就是把狄利克雷卷积 \Rightarrow 一般多项式卷积。
- 定理 ： 两个数论函数相狄利克雷卷积，其贝尔级数相乘。
下面给出一些常见的贝尔级数 :
-
e\quad\Rightarrow\quad1
-
I\quad\Rightarrow\quad\sum\limits_{i=0}^{\infty}x^i=\frac{1}{1-x}
-
id_k\quad\Rightarrow\quad\sum\limits_{i=0}^{\infty}p^{ik}x^i=\frac{1}{1-p^kx}
-
I^{-1}=\mu\quad\Rightarrow\quad \left(\frac{1}{1-x}\right)^{-1}=1-x
由此可以自然地得出 \mu 的定义式.
-
\mu^2\quad\Rightarrow\quad 1+x
-
d\quad\Rightarrow\quad\sum\limits_{i=0}^{\infty}ix^i=\frac{1}{(1-x)^2}
可与 I*I=d 互推。
-
σ_k\quad\Rightarrow\quad\sum\limits_{i=0}^{\infty}x^i\sum\limits_{j=0}^ip^{jk}=\frac{1}{(1-x)(1-p^kx)}
可与 I*id_k=σ_k 互推。
-
\varphi\quad\Rightarrow\quad 1+\sum\limits_{i=1}^{\infty}p^{i-1}(p-1)x^i
\qquad\qquad\ \ =1+\frac{p-1}{p}(\sum\limits_{i=0}^{\infty}p^{i}x^i-1)
- $w(n)=2^\text{n的不同质因子数}$ ,显然有 $w(p^k)=2
w\quad\Rightarrow\quad1+\sum\limits_{i=1}^{\infty}2x^i=\frac{1+x}{1-x}
这能推出 w=\mu^2*I
另外,点积对贝尔级数也可以产生影响,一般是点积完全积性函数。
点积 e 相当于变成 e ，点积 I 则不变。
点积 id 对函数贝尔级数的影响：把 x 代换成 p^kx ,证明:
-
F·id_k\Longrightarrow \sum\limits_{i=1}^{\infty}F(p^i)p^{ki}x^i=\sum\limits_{i=1}^{\infty}F(p^i)(p^kx)^i
将 p^kx 看作整体即可。
下面给出一些例子:
先写出 f 的贝尔级数 ： F_p(x)=1+\sum\limits_{k=1}\big((-1)^k+p^k\big)=\frac{1}{1+x}+\frac{1}{1-px}-1
接下来构造卷积，令 G_p(x)=(1+x)(1-px) 可得 (G*F)_p(x)=(1+x)+(1-px)-(1+x)(1-px)=1+px^2。
对于 $1+px^2$ 对应的函数 $h$，满足 $h(n)$ 非 $0$ 的 $n$ 满足所有素因子次数均为 $2$。
也即 $n=d^2$ 且 $\mu^2(d)$。
可得 $S_h(n)=\sum\limits_{d=1}^{\sqrt{n}}i\mu^2(i)$ ，这是易求的。
# ${\mathscr P}\!art\ 3$ : powerful number
$\rm zzq$ 大爷说这是杜教筛的拓展,所以就一起讲了。
**定义** : $\text{powerful number}$ 是 **没有 $\bf 1$ 次质因子** 的数。也简称为 $\rm PN$。
一个强有力的结论 : $n$ 以内 $\rm PN$ 的个数为 $O(\sqrt{n})$ 。
- **证明** :
所有PN必然可表示成 $a^2b^3$ 的形式,恰好偶数次的素因子塞到 $a$ 里面,奇数次的素因子塞一次 $b$ 。(这构成一个单射)
考虑枚举 $a$ 考虑满足条件的 $b$ 个数,得 $\sum\limits_{a=1}^{\sqrt{n}}(n/a^2)^{1/3}$ ,积分得到 $O(\sqrt{n})$.
- 应用方法 : **拟合法**
**例题①** : [P5325 【模板】Min_25筛](https://www.luogu.com.cn/problem/P5325)
（对你没看错，这玩意可以硬干 Min_25 筛板子）
**题意** : 设 $F(p^k)=p^k(p^k-1)$ ,求 $S_F(n)
有F(p)=p(p-1) ,构造函数 G(x)=x\varphi(x) ,显然其是积性函数。
而且我们发现 G(p)=F(p) ,这称作素数拟合,至于为什么要这么构造后面再讲。
设数论函数 H(n) 满足 F=G*H ,即 H=F/G (狄利克雷卷积除法)。
这里给出几个结论 (相关证明左转 莫比乌斯反演与数论函数 ) ：
这就保证了 H 的合法性,而且我们可以得到 H 也是积性函数。
观察到 F=G*H\rightarrow F(p)=G(1)H(p)+G(p)H(1)=H(p)+G(p)
由于F(p)=G(p),可以得到H(p)=0.
又因为积性,所以 H(n) 有值的地方都是 \bf PN! (这就是拟合的原因)
\sum\limits_{i=1}^nF(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}H(d)G(\frac{i}{d})
=\sum\limits_{d=1}^nH(d)\sum\limits_{d|i}^nG(\frac{i}{d})
=\sum\limits_{d=1}^nH(d)S_G(\lfloor n/d\rfloor)
=\sum\limits_{d=1}^n[d∈PN]H(d)S_G(\lfloor n/d\rfloor)
我们对 G 进行块筛,然后 O(\sqrt{n}) 筛出 \rm PN ,并求出对应的 H(d) 就好了。
这里 G(n)=x\varphi(x) ,明显可以杜教筛,剩下的问题就是求出 O(\sqrt{n}) 个 H(n) 了。
首先生成所有的 \rm PN ,方法是 : 枚举 p^c(c>1;p\leq\sqrt{n}) ，dfs 搜索即可,这里还顺便得到了分解。
由 F=G*H 可得 F(p^k)=\sum\limits_{c=0}^kG(p^c)F(p^{k-c})。
移项得到 H(p^k)=F(p^k)-\sum\limits_{c=0}^{k-1}H(p^c)*G(p^{k-c}) (类似多项式求逆)
-
求值复杂度分析
素数密度为 O(\frac{\sqrt{n}}{\log n}) ,对于每个素数复杂度为 O(log_p^2n)。
这部分复杂度可以估计为 O\Big(\sum\limits_{i=1}^{\sqrt{n}}\log_i^2n/\log n\Big)=O\Big(\sum\limits_{i=1}^{\sqrt{n}}\frac{\log^2n}{\log^2i}/\log n\Big)=O\Big(\log n\sum\limits_{i=1}^{\sqrt{n}}\frac{1}{\log^2i}\Big)
积分不太会积，但是容易说明 O\Big(\sum\limits_{i=1}^{n}\frac{1}{\log^2i}\Big)=O(\sqrt{n}/\log^2n)。
当 i\leq n^{1/3}(分界是随便取的) 时，显然贡献不超过 O(n^{1/3})。
当 i>n^{1/3} 时，有 O(\log^2i)=O(\log^2n) ，则这部分贡献不超过 O(\sqrt{n}/\log^2n)。
综上，复杂度为 O(\sqrt{n}/\log n)。(可能有细微偏差，反正肯定不超过 O(\sqrt{n}))
求出需要的 H(p_k) 之后，再利用积性，不难得到函数值。
算上杜教筛,总的复杂度 O(n^{2/3}) ,但还是跑不过Min_25……
#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long
#define MaxS 5660000
using namespace std;
const int
mod=1000000007,
Inv2=500000004,
Inv6=166666668;
int lim,lp,tn,p[MaxS];
ll N,G[MaxS],tH[10005][35];
void sieve()
{
G[1]=1;
for (int i=2;i<=lim;i++){
if (!G[i]){p[++tn]=i;G[i]=i-1;}
for (int j=1;j<=tn&&p[j]*i<=lim;j++){
if (i%p[j]==0)
{G[p[j]*i]=G[i]*p[j];break;}
G[p[j]*i]=G[i]*(p[j]-1);
}G[i]=(G[i-1]+G[i]*i)%mod;
}
for (lp=1;1ll*p[lp]*p[lp]<=N;lp++);
ll tG[35];
for (int i=1;i<=lp;i++){
ll x=1ll*p[i]*p[i],sq=x%mod;
tG[0]=tH[i][0]=1;
tG[1]=1ll*p[i]*(p[i]-1)%mod;
for (int k=2;x<=N;x*=p[i],k++){
tG[k]=tG[k-1]*sq%mod;
tH[i][k]=(x%mod)*(x%mod-1)%mod;
for (int c=0;c<k;c++)
tH[i][k]=(tH[i][k]-tH[i][c]*tG[k-c])%mod;
}
}
}
ll _S[2005];
//(phi.id)*id=id2
ll S(ll n)
{
if (n<=lim)return G[n];
if (_S[N/n])return _S[N/n];
ll sum=0,l=2,r;
for (;l<=n;l=r+1){
r=n/(n/l);
sum=(sum+S(n/l)*((r-l+1)%mod)%mod*((l+r)%mod))%mod;
}sum=mod-sum*Inv2%mod;
ll buf=n%mod; buf=buf*(buf+1)%mod*(buf*2+1)%mod*Inv6;
return _S[N/n]=(buf+sum)%mod;
}
ll ans;
void dfs(ll n,ll num,int t)
{
ans=(ans+num*S(N/n))%mod;
for (int i=t;i<=lp;i++){
if (1ll*p[i]*p[i]>N/n)return ;
int k=2;
for (ll x=1ll*p[i]*p[i];x*n<=N;k++,x*=p[i])
dfs(n*x,num*tH[i][k]%mod,i+1);
}
}
int main()
{
scanf("%lld",&N);
lim=max((int)pow(N,0.675)+5,100);
sieve();dfs(1,1,1);
printf("%lld",(ans+mod)%mod);
return 0;
}
给出一个积性函数 F(n) ,求 S_F(n) 。
构造一个易块筛的积性函数 G(n) ,满足 G(p)=F(p) ,即素数拟合。
接着构造 H=F/G ,不难得到 H(p)=0 , H 有值的地方均是 \rm PN。
能得到 S_F(n)=\sum\limits_{d=1}^n[d∈PN]H(d)S_G(\lfloor n/d\rfloor)
接下来干两件事 : 对于 G 块筛 + 求出 O(\sqrt{n}) 个 H(d)。
值得注意的是,对于 F 块筛并不是一件困难的事。
使用 \rm PN 求和一次是 O(\sqrt{n}) 的，配合线性筛预处理，复杂度分析和杜教筛相同，为 O(n^{2/3})。
其实还可以做到 O(n^{3/5})。
-
定理 ： 若 G 只在 \rm PN 处有值，那么 G 的块筛只有 O(n^{1/3}) 个本质不同的值。
在 S_G(\lfloor n/i\rfloor) 中，若 i>N^{1/3} ，则 \lfloor n/i\rfloor\leq N^{2/3} ，这部分只有 O(\sqrt{N^{2/3}})=O(N^{1/3}) 个有值的 G ，前缀和也就只会变化 O(N^{1/3}) 次。
若 i\leq N^{1/3} ，显然只有 O(N^{1/3}) 个。
F=G*H\Rightarrow S_F(n)=\sum\limits_{d=1}^nG(d)S_H(\lfloor n/d\rfloor)
由于只有 O(n^{1/3}) 个本质不同的 S_G ，该式计算复杂度可降至 O(n^{1/3})。
若线性筛预处理到 T ，复杂度为 O\Big(T+\sum\limits_{i=1}^{N/t}(N/i)^{1/3}\Big)=O(T+N/T^{2/3}) ,令 T=N^{3/5} 可得最优复杂度为 O(N^{3/5})。
例题② : 『奇怪的函数』
题意 : 有积性函数 F(p^c)=p^{ck_1}+p^{ck_2} ,求 S_F(n) ， n\leq 10^{12},k_1,k_2\leq 10。
考虑函数 G=id_{k_1}*id_{k_2} ，显然有 G(p)=p^{k_1}+p^{k_2}。
容易通过插值 O\big((k_1+k_2)\sqrt{n}\big) 求出 id_{k_1},id_{k_2} 的块筛。
观察最后转化的式子 $S_F(n)=\sum\limits_{d=1}^n[d∈PN]H(d)S_G(\lfloor n/d\rfloor)
对于每个 \rm PN 整除分块计算对应的 S_G(n) ，复杂度为 O\Big(\sum\limits_{a,b}\sqrt{n/a^2b^3}\Big)=O\Big(\sum\limits_{a}\sqrt{n}/a\Big)=O(\sqrt{n}\log n)。
综合应用 ：冷群筛
通过前面的讨论，我们已经得到如下的结论 :
我们可以拿已知可筛的函数卷积组合成目标函数来解决问题。
为了方便构造,我们可以预先构造出一些函数。
我们只关心贝尔级数的 $[x^1]$ 项，由于常数项都为 $1$ 两个贝尔级数相乘在 $[x^1]$ 处表现为相加。
前面已经知道如何筛 $\mu·id_k$ 了，即 $1-p^kx$，现在我们可以单点 $-1$。
接下来看看如何单点加一，不难发现 $id_{k}(p)=p^k$ 即可满足要求。
下面来解决一个经典的问题 : $\rm Min_25$ 筛问题。
**题意** : 对于一个积性函数 $F(n)$ ,满足 $F(p)$ 是关于 $p$ 的 $m$ 次多项式（ $m$ 较小 ）, $F(p^k)$ 能快速计算,求 $F$ 的块筛。
考虑利用 $\rm PN$:
构造一个易于块筛的积性函数 $G(n)$ ,满足 $G(p)=F(p)$ ,即素数拟合。
根据 $\rm PN$ 的经典结论,我们只需要得到 $G$ 的块筛,就能够在 $O(n^{3/5})$ 的时间内转化为 $F$ 的块筛。
构造 $G(p)=F(p)$ 相当于钦定了 $G$ 的贝尔级数的 $[x^1]$ 项。
设 $F(p)=\sum\limits_{i=0}^mc[i]p^i$ ，即题面中的低次多项式。
利用卷积，我们可以在某个 $[x^1p^c]$ 处 $±1$。
使用加法倍增即可,需要 $O(m\log S)$ 次杜教筛,比Min_25不知慢到哪里去了Orz。
不过大多数时候,出题人的函数比较有“数论意义(?)”,这个 $c$ 大部分都是 $±1$ ,此时就是 $O(m)$ 次杜教筛,效率还是可以的。
这估计也论证了杜教筛是不可能打过Min_25筛这种毒瘤东西的……
upd : 这种筛法投到UOJ群的时候突然冷群了,被命名为"冷群筛"/kel