积性函数&莫比乌斯反演&筛法学习笔记

积性函数&莫比乌斯反演&筛法

符号约定

$P$ 表示质数集合

在不加说明的情况下， $p$ 为某个质数， $p_i$ 表示从小到大第 $i$ 个质数，且 $p_0=1$

$\text{minp}(x)$ 表示 $x$ 的最小质因子

数论函数

定义在正整数域上的函数，值域在正整数域上的函数称为数论函数

狄利克雷卷积

对于两个数论函数 $f,g$ 定义其狄利克雷卷积为 $(f*g)(n)=\sum_{d|n}f(d)g(\frac n d)$

狄利克雷卷积有如下性质

交换律： $f*g=g*f$
结合律： $f*(g*h)=(f*g)*h$
分配律： $f*(g+h)=f*g+f*h$
有单位元 $\epsilon$
若 $f,g$ 均为积性函数，则 $f*g$ 也为积性函数

证明下性质5

(f*g)(ij)=\sum_{d|ij}f(d)g(\frac {ij} d),i\perp j\\(f*g)(ij)=\sum_{d_1|i}\sum_{d_2|j}f(d_1d_2)g(\frac {ij}{d_1d_2})=\sum_{d_1|i}\sum_{d_2|j}f(d_1)f(d_2)g(\frac i {d_1})g(\frac j{d_2})\\=(\sum_{d_1|i}f(d_1)g(\frac i{d_1}))(\sum_{d_2|j}f(d_2)g(\frac j{d_2}))=(f*g)(i)(f*g)(j)

积性函数

若一个数论函数 $f$ 满足 $f(1)=1 \ \text{and} \ \forall \gcd(i,j)=1\to f(ij)=f(i)f(j)$ ，我们则称它是积性函数

特别的，对于满足 $\forall i,j,f(i*j)=f(i)*f(j)$ 的数论函数 $f$ ,我们称它是完全积性函数

常见的积性函数

元函数： $\epsilon(n)=[n=1]$

恒等函数： $I(n)=1$

单位函数： $id(n)=n$

幂函数： $id_k(n)=n^k$

约数个数函数： $d(n)$ 或 $\sigma_0(n)$

约数和函数： $\sigma(n)$

除数函数： $\sigma_k(n)$

欧拉函数： $\varphi(n)$

莫比乌斯函数： $\mu(n)=\begin{cases}1,n=1\\(-1)^k,n为k个不同质数之积\\0,n有平方因子\end{cases}$

积性函数的筛法

我们可以利用欧拉筛在线性时间内筛出任意积性函数 $f$

对于欧拉筛我们只需讨论两种情况

$i\perp p,p\space is \space prime,f(ip)=f(i)(p)$
$i=p^kj,j\perp p,p\space is\space prime,f(ip)=f(j)f(p^{k+1})$

对于不同的数论函数具体讨论即能求出

小结论

$\mu*I=\epsilon$

记n有k个不同素因子

$(\mu*I)(n)=\sum_{d|n}\mu(d)=\sum_{i=0}^k(-1)^k\tbinom k i=(1-1)^k=[k=0]=[n=1]$
$\varphi*I=id$

即 $\sum_{d|n}\varphi(d)=n$

这个的证明考虑分母为n的n个真分数，约分后分子分母互质且每一个分母 $d$ 出现次数为 $\varphi(d)$

考虑每一个分母为 $d$ 的，分子与 $d$ 互质的 $\varphi(d)$ 个分数大小不一且唯一

同时乘上 $\frac n d$ 后，分子一一对应 $[1,n]$
$\mu *id=\varphi$

考虑结论2与结论1

$\mu*id=\mu*\varphi*I=(\mu*I)*\varphi=\epsilon*\varphi=\varphi$

莫比乌斯反演

根据我们已经学会的结论，我们能轻松得到莫比乌斯反演的公式了

$f*I=g\iff g*\mu=f$

由结论1可证

$g(n)=\sum_{d|n}f(d)\iff f(n)=\sum_{d|n}\mu(d)g(\frac n d)$

通过结论1，我们也有

$\sum_{d|n}\mu(d)=[n=1]$

经典式子推导

默认 $n\leq m$

复杂度记号 $O(T_1)-O(T_2)$ 表示预处理 $O(T_1)$ 单次询问 $O(T_2)$

$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]$

套路莫反一波

$\sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\mu(d)$

考虑直接枚举 $\gcd(i,j)$ 的因数 $d$

$\sum_{d=1}^{n}\sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d}\mu(d)\\\sum_{d=1}^{n}\mu(d)\lfloor\frac n d\rfloor\lfloor\frac md \rfloor$

通过欧拉筛预处理 $\mu$ 和整除分块可以做到 $O(n)-O(\sqrt n）$
$\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)$

套路枚举 $\gcd$

$\sum_{d=1}^{n}d\sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d}[\gcd(i,j)=1]$

右边是我们熟悉的问题1，转化为

$\sum_{d=1}^{n}d\sum_{g=1}^{\frac n d}\mu(g)\lfloor\frac n{dg}\rfloor\lfloor\frac m {dg} \rfloor$

直接计算这个式子复杂度是 $O(\sum_{d=1}^{n}\sqrt\frac n d)=O(n)$

考虑枚举 $t=dg$ 交换一波和式

$\sum_{t=1}^{n}\lfloor\frac n t\rfloor\lfloor\frac m t\rfloor\sum_{d|t}d\mu(\frac t d)$

不难发现第二重和式就是 $(\mu*id)(t)=\varphi(t)$

简化为

$\sum_{t=1}^{n}\lfloor\frac n t\rfloor\lfloor\frac m t\rfloor\varphi(t)$

通过欧拉筛预处理 $\varphi$ 和整除分块同样可以做到 $O(n)-O(\sqrt n）$
$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1]ij$

类似问题1

先套路莫反

$\sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\mu(d)ij=\sum_{d=1}^nd^2\mu(d)\sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d}ij\\=\sum_{d=1}^nd^2\mu(d)\frac{(\lfloor\frac n d\rfloor+1)\lfloor\frac n d\rfloor(\lfloor\frac m d\rfloor+1)\lfloor\frac m d\rfloor}4$

预处理 $id_2\mu$ ，整除分块可以做到 $O(n)-O(\sqrt n）$
$\sum_{i=1}^n\sum_{j=1}^m\text{lcm}(i,j)$

由于 $\text{lcm}$ 并没有 $\gcd$ 那么优美的性质，我们一般将其转化为 $\gcd$ 计算

$\sum_{i=1}^n\sum_{j=1}^m\frac {ij}{\gcd(i,j)}\\=\sum_{d=1}^n\frac 1 d\sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d}[\gcd(i,j)=1]idjd\\=\sum_{d=1}^nd\sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d}[\gcd(i,j)=1]ij$

第二三重和式为问题3

简化为

$\sum_{d=1}^nd\sum_{g=1}^{\frac n d}g^2\mu(g)\frac{(\lfloor\frac n {dg}\rfloor+1)\lfloor\frac n {dg}\rfloor(\lfloor\frac m {dg}\rfloor+1)\lfloor\frac m {dg}\rfloor}4$

由于这个部分式子不够优美，不能像问题2那样凑出一个优美的狄利克雷卷积

我们直接整除分块套两次处理这个问题

记 $f(n,m)=\sum_{d=1}^nd^2\mu(d)\frac{(\lfloor\frac n d\rfloor+1)\lfloor\frac n d\rfloor(\lfloor\frac m d\rfloor+1)\lfloor\frac m d\rfloor}4$

$ans=\sum_{d=1}^ndf(\lfloor\frac n d\rfloor,\lfloor\frac m d\rfloor)$

时间复杂度 $O(??)$ 不太会算复杂度，如果记忆化后大概比线性略优
$d(ij)=\sum_{x|i}\sum_{y|i}[\gcd(x,y)=1]$

约数个数的经典转化

这里放出Siyuan大佬的证明
$\sum_{i=1}^n\sum_{j=1}^md(ij)$

运用问题5的结论，交换和式得

$\sum_{d=1}^n\mu(d)\sum_{x=1}^{\frac n d}\sum_{y=1}^{\frac m d}\lfloor\frac n{xd}\rfloor\lfloor\frac m{yd}\rfloor$

可以做到 $O(n)-O(\sqrt n)$

筛法

~~开始简单科技了~~

快速求得 $\sum_{i=1}^nf(i)$ ， $f$ 为某个数论函数

由于各种毒瘤出题人的存在，我们的式子可能已经难以更进一步了，达到了线性的优异复杂度

很多时候，式子的瓶颈均在线性筛上（毕竟这玩意是线性的），我们需要更优的方法筛出某个积性函数

更高深的奇怪筛法大多能在比线性略低的复杂度做到这一点

杜教筛

杜教筛的原理很简单，考虑一个性质优异的积性函数 $g$ 与 $f$ 卷一起的前缀和

$\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac i d)=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}f(i)$

我们敏锐的观察到后面的式子是 $f$ 的前 $\lfloor \frac n d\rfloor$ 项和

考虑把 $d=1$ 的一项提出来， $\sum_{i=1}^{n}(f*g)(i)=g(1)\sum_{i=1}^nf(i)+\sum_{d=2}^ng(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}f(i)$

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

只要 $g$ 的性质足够优越，使得 $f*g,g$ 的前缀和均能快速求得且前面一项可通过整除分块降低复杂度

我们便成功的达到了我们的目的——降低复杂度

若 $(f*g)(n)$ 的前缀和计算复杂度为 $T_0(n)$ ， $\sum_{i=1}^nf(i)$ 的计算复杂度为 $T_1(n)$

由于我们共需运算 $\sqrt n$ 个 $f$ 的前缀和，算上整除分块的复杂度与 $\sqrt n$ 个取值，枚举取值 $i$

则 $T_1(n)=\sum_{i=1}^{\sqrt n}O(\sqrt i)+O(\sqrt{\frac n i})=O(n^{\frac 3 4})$

我们还能再优化一点，考虑线性筛筛出 $f$ 前 $M$ 的取值

复杂度 $T_1(n)=\sum_{i=1}^{\lfloor\frac n M\rfloor}O(\sqrt{\frac n i})=O(\frac n{\sqrt M})+O(M)$

$M=n^{\frac 2 3}$ 时复杂度最优

复杂度分析不懂.jpg

经典例子

$\sum_{i=1}^n\varphi(i)$

直接考虑 $\varphi*1=id$

显然我们容易求 $id,1$ 的前缀和
$\sum_{i=1}^n\mu(i)$

考虑 $\mu*1=\epsilon$

$1,\epsilon$ 的前缀和不要太弱智
$\sum_{i=1}^n\varphi(i)i^k$

考虑 $(\varphi\cdot id_k)*id_k=id_{k+1}$

$((\varphi\cdot id_k)*id_k)(n)=\sum_{d|n}\varphi(d)d^k(\frac n d)^k=n^k\sum_{d|n}\varphi(d)=n^{k+1}$

$id_k$ 的前缀和可以插值，或斯特林数，伯努利数等方法求出

Min_25筛

相比与杜教筛的使用条件，Min_25更为通用

Min_25筛能处理所有在 $f(p)$ 处取值为关于p的低阶多项式且 $f(p^c)$ 能快速求值的数论函数前缀和问题

求 $\sum_{i=1}^nf(i)$ ，设 $m=\sqrt n内质数个数$

思路

由于 $f(p)$ 是关于 $p$ 的低阶多项式，我们只需求多项式每一项相加即可

首先，我们试图求出

$G_k(n)=\sum_{i=1}^n[i\in P]i^k$

由于 $G_k(n)$ 并不好求，我们考虑通过dp $F(i,n)$ 得到 $G_k(n)$

$F_k(i,n)=\sum_{x=1}^n[x\in P\space or\space \text{minp}(x)>p_i]x^k$

显然， $F_k(m,n)=G_k(n)$

同时， $F_k(0,n)=S_k(n)=\sum_{x=1}^nx^k$ ，上自然数幂之和可得，dp过程暂不展开

接下来考虑设计一个dp计算答案

$S(i,n)=\sum_{x=2}^nf(x)[\text{minp}(x)>p_i]$

注意没有计算 $f(1)$

考虑最终答案显然为 $S(0,n)$

显然我们知道 $S(m,n)=0$

求解 $S(i,x)$ 的过程中会用到 $G_k(x)$ 的信息

Part 1

$F_k(i,n)\to F_k(i+1,n)$

我们仅需考虑去掉 $\{x|\text{minp}(x)=p_{i+1}\}$ 的贡献

记 $x=y*p_{i+1},\text{minp}(y)>p_i$

$F_k(i+1,n)=F_k(i,n)-(F_k(i,\lfloor\frac n {p_{i+1}}\rfloor)-G_k(p_i))p_{i+1}^k$

考虑减去所有y的贡献

$F_k(i,\lfloor\frac n {p_{i+1}}\rfloor)$ 但多算了这里面的质数部分，即 $G_k(p_i)$

由于 $i\leq m$ ，考虑线性筛预处理一部分 $G_k(p_i)$ 即可

Part 2

$S(i+1,n)\to S(i,n)$

我们直接暴力枚举 $p_{i+1}^e$ 的指数 $e$

$S(i,n)=S(i+1,n)+\sum_{e=1}f(p_{i+1}^e)(S(i+1,\lfloor \frac n {p_{i+1}^e}\rfloor)+1)$

具体实现时我们考虑用Part 1中的 $G_k$ 计算 $\sum_{j=i+1}f(p_j)$

我们得以计算 $\text{minp}(x)\geq p_m$ 的部分

具体实现

由于我们需要存储许多关于 $\lfloor\frac n i\rfloor$ 的信息

我们可以利用我们熟知的整除分块中这类数的性质，只有 $2\sqrt n$ 种取值，离散化即可

考虑将值域在 $\sqrt n$ 内的部分用 $ind1$ 查出离散化后的编号

值域大于 $\sqrt n$ 的部分将 $\lfloor\frac n i\rfloor$ 存入 $ind2$ 以便查询

以洛谷模板给出代码

【模板】Min_25筛

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxsn=1e5+5,mod=1e9+7;
int iv2,iv3;
ll n,m;
int tot;
ll val[2*maxsn];
int ind1[maxsn],ind2[maxsn];
int f1[2*maxsn],f2[2*maxsn];
ll read(){
    ll x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
inline int add(int x){
    if(x>=mod)x-=mod;
    return x;
}
inline int sub(int x){
    if(x<0)x+=mod;
    return x;
}
inline int power(int x,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod;
        b>>=1;
    }
    return ans;
}
bool bj[maxsn];
int len;
int p[maxsn];
int id[maxsn],id2[maxsn];
void pre(){
    m=sqrt(n);
    for(int i=2;i<=m;i++){
        if(!bj[i]){
            p[++len]=i;
            id[len]=add(id[len-1]+i);
            id2[len]=add(id2[len-1]+1ll*i*i%mod);
        }
        for(int j=1;1ll*i*p[j]<=m&&j<=len;j++){
            bj[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
    return ;
}
int S(int i,ll x){
    if(p[i]>=x)return 0;
    int k=(x<=m?ind1[x]:ind2[n/x]);
    int ans=sub(sub(f2[k]-f1[k])-sub(id2[i]-id[i]));
    for(int j=i+1;j<=len&&1ll*p[j]*p[j]<=x;j++){
        ll pr=p[j];
        for(int e=1;pr<=x;e++,pr=pr*p[j]){
            int v=pr%mod;
            ans=add(ans+1ll*v*(v-1)%mod*(S(j,x/pr)+(e!=1))%mod);
        }
    }
    return ans;
}
int main(){
    n=read();
    iv2=power(2,mod-2);iv3=power(3,mod-2);
    pre();
    for(ll l=1,r=0;l<=n;l=r+1){
        ll v=n/l;
        r=n/v;
        val[++tot]=v;
        if(v<=m)ind1[v]=tot;
        else ind2[n/v]=tot;
        v=v%mod;
        f1[tot]=1ll*v*(v+1)%mod*iv2%mod;f1[tot]--;
        f2[tot]=1ll*v*(v+1)%mod*(2ll*v%mod+1)%mod*iv2%mod*iv3%mod;f2[tot]--;
    }
    for(int i=1;i<=len;i++){
        for(int j=1;1ll*p[i]*p[i]<=val[j]&&j<=tot;j++){
            int k=(val[j]/p[i]<=m?ind1[val[j]/p[i]]:ind2[n/(val[j]/p[i])]);
            f1[j]=sub(f1[j]-1ll*sub(f1[k]-id[i-1])*p[i]%mod);
            f2[j]=sub(f2[j]-1ll*sub(f2[k]-id2[i-1])*p[i]%mod*p[i]%mod);
        }
    }
    printf("%d\n",add(S(0,n)+1));
    return 0;
}