莫反及杜教筛前置知识小记

目录

移植于原csdn博客

莫比乌斯函数

首先把(n)按照唯一分解定理变成(largeprod_{i=1}^{k}p_i^{c_i})
那么若(forall xin p)

[mu(n)=egin{cases}1,n=1\0,n=qx^2\(-1)^k,otherwiseend{cases} ]

那么就可以用线性筛来解决，代码

inline void init(){
    mu[1]=1; register int m=0;
    for (register int i=2;i<=N;++i){
        if (!v[i]) v[i]=i,prime[++m]=i,mu[i]=-1;
        for (register int j=1;j<=m&&prime[j]<=N/i;++j){
            v[prime[j]*i]=prime[j];
            if (i%prime[j]==0) break;
            mu[prime[j]*i]=-mu[i];
        }
    }
}

整除分块

Example

求

[sum_{i=1}^nlfloorfrac{n}{i} floor ]

分析

可以感性理解，一个数(n)最多有(2sqrt n)中取值，那么其实只有(2sqrt n)次枚举是有意义的；
当然，也可以理解成只有正好(largelfloorfrac{n}{i} floor=frac{n}{i})才是需要枚举的，
因为其它取值都可以等同于下取整，所以枚举(n)的约数个数次是最优的，不管怎样，其实也是容易理解的

代码

register int ans=0;
for (register int l=1,r;l<=k;l=r+1){
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}
相关
洛谷 2261 余数之和
洛谷 1447 能量采集（我知道可以(O(n))过）
洛谷 3935 Calculating(approx)洛谷 2424 约数和
洛谷 2280 模积和(approx)洛谷 2834 能力测验

莫反常用性质

欧拉函数的性质（常用）

[sum_{d|n}varphi(d)=n ]

证明：设(f(n)=sum_{d|n}varphi(d))

那么(f)是积性函数，(f=varphi*I)

显然可以对质数的指数幂单独处理，

(f(p^c)=varphi(1)+varphi(p)+dots+varphi(p^c)=p^c)

那么(f(n)=prod f(p^c)=n)

另一种证法：将(frac{1sim n}{n})化简后按照分母升序排列

那么分母的种类显然有(d(n))个，而分子(x)想要在特定的分母(d)出现

必须满足(x<d且gcd(x,d)=1)，那么就是(varphi(d))个分子，由于一共写出(n)个分数，

那么(sum_{d|n}varphi(d)=n)

莫比乌斯函数的性质

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

证明：若(n)存在最小质因子(mn)，且它的最高指数幂为({mn}^k)，
那么

[large sum_{d|n}mu(d)=sum_{d|frac{n}{{mn}^k}}mu(d)+sum_{d|frac{n}{{mn}^k}}mu(d*mn)+dots+sum_{d|frac{n}{{mn}^k}}mu(d*{mn}^k) ]

当(k>1)时后面的部分均为0,所以该式子化简为

[large sum_{d|n}mu(d)=sum_{d|frac{n}{{mn}^k}}mu(d)+sum_{d|frac{n}{{mn}^k}}mu(d*mn) ]

当(mu(d)=0)时，(mu(d*mn)=0)
当(mu(d) eq 0)时，(mu(d*mn)=-mu(d))
所以该式子最后化简为

[large sum_{d|n}mu(d)=sum_{d|frac{n}{{mn}^k}}mu(d)-sum_{d|frac{n}{{mn}^k}}mu(d)=0 ]

当(n)不存在质因子时，即(n=1)时，(sum_{d|n}mu(d)=1)
综上所述，(sum_{d|n}mu(d)=[n==1])
这是第一条性质，比较常用

[sum_{d|n}frac{mu(d)}{d}=frac{varphi(n)}{n} ]

第二条性质在狄利克雷卷积部分证明

莫比乌斯反演（常用）

约数定义法

若(F(n))和(f(n))是非负整数集合中的两个函数，且满足

[F(n)=sum_{d|n}f(d) ]

那么

[f(n)=sum_{d|n}mu(d)F(frac{n}{d}) ]

证明：

[sum_{d|n}mu(d)F(frac{n}{d})=sum_{d|n}mu(d)sum_{k|frac{n}{d}}f(k) ]

[=sum_{k|n}f(k)sum_{d|frac{n}{k}}mu(d)=f(n) ]

倍数定义法

若(F(d))和(f(d))是非负整数集合中的两个函数，且满足

[F(d)=sum_{d|n}f(n) ]

那么

[f(d)=sum_{d|n}mu(frac{n}{d})F(n) ]

证明：

[sum_{d|n}mu(frac{n}{d})F(n)=sum_{d|n}mu(frac{n}{d})sum_{n|k}f(k) ]

考虑枚举(k)，令(n)表示原来的(frac{n}{d})，那么

[=sum_{d|k}f(k)sum_{nd|k}mu(n)=sum_{d|k}f(k)sum_{n|frac{k}{d}}mu(n) ]

根据莫比乌斯函数的性质(sum_{d|n}mu(d)=[n==1])，可以得到

[=sum_{d|k}f(k)[frac{k}{d}==1]=f(d) ]

得证

洛谷 5176 需要用到的gcd的性质

[gcd(ij,jk,ik)=frac{gcd(i,j)gcd(i,k)gcd(j,k)}{gcd(i,j,k)} ]

积性函数

定义

对于一个数论函数(f)，且(f(1)=1),满足任意两个互质的整数(p,q)

都满足(f(pq)=f(p) imes f(q))，那么这个函数就是积性函数

特别地，若任意整数(p,q)都满足(f(pq)=f(p) imes f(q))，那么就是完全积性函数

Example（积性函数）

  1. 莫比乌斯函数：(mu(n))
  2. 欧拉函数：(varphi(n)=sum_{i=1}^n[gcd(n,i)==1])
  3. 约数个数：(d(n)=sum_{d|n}1)
  4. 约数和函数：(sigma(n)=sum_{d|n}d)

完全积性函数

  1. 元函数：(epsilon(n)=[n==1])
  2. 恒等函数：(I(n)=1)
  3. 单位函数：(id(n)=n)

狄利克雷卷积

定义

两个数论函数(f,g)的卷积为((f*g)(n)=sum_{d|n}f(d)*g(frac{n}{d}))，一般后面括号省略不写，默认为(n)
感性理解，它满足交换律、结合律和分配率，即
交换律：((f*g)=(g*f))
结合律：(((f*g)*h)=(f*(g*h)))
分配率：(((f+g)*h)=(f*h)+(g*h))
可以知道((f*epsilon)=f)

证明性质

换一种方法证明莫比乌斯反演

[f(n)=sum_{d|n}F(d) imes mu(frac{n}{d}) ]

已知(F(n)=sum_{d|n}f(d))

也就是(F=(f*I))

同时卷上(mu)得到

(F*mu=f*I*mu)

已知(sum_{d|n}mu(d)=[n==1])

也就是(mu*I=epsilon)

所以

[F*mu=f*epsilon=f ]

综上所述(f=F*mu)

再来证明

[sum_{d|n}frac{mu(d)}{d}=frac{varphi(n)}{n} ]

根据欧拉函数的性质(sum_{d|n}varphi(d)=n)

也就是(varphi*I=id)

同乘(mu)得到

(varphi*I*mu=id*mu)

所以

[varphi*epsilon=varphi=id*mu ]

即

[varphi(n)=sum_{d|n}d*mu(frac{n}{d}) ]

同除(n)得到

[frac{varphi(n)}{n}=sum_{d|n}frac{mu(d)}{d} ]

狄利克雷卷积的一大性质就是
若(h=(f*g))且(f,g)为积性函数，那么(h)也是积性函数
简单证明，若(gcd(a,b)=1)

[h(ab)=sum_{d|ab}f(d)*g(frac{ab}{d}) ]

[=sum_{d1|a}sum_{d2|b}f(d1d2)*g(frac{ab}{d1d2}) ]

在这一条，必须得满足(gcd(d1,d2)=1)，不然显然会算重。

[=sum_{d1|a}f(d1)*g(frac{a}{d1})sum_{d2|b}f(d2)*g(frac{b}{d2})=h(a)*h(b) ]

那么(h(ab)=h(a)*h(b))
积性函数的一大优点就是可以先处理出质数指数幂的答案再分别相乘

洛谷 4466 和与积

题目

求有多少对((a,b))满足(1leq a<bleq n)且(a+b|ab)

分析

若(gcd(a,b)=1),那么(a+b∤ab)

若(gcd(a,b) eq 1),设(d=gcd(a,b),i=da,j=db)

( herefore (i+j)|ijd)

(ecause)若(gcd(a,b)=1),那么(a+b∤ab)

( herefore (i+j)|d)

也就是求有多少个三元组((i,j,d))，满足(id,jdleq n,gcd(i,j)=1,(i+j)|d)

那么

[=sum_{i=1}^{n}sum_{j=1}^{i-1}lfloorfrac{lfloorfrac{n}{i} floor}{i+j} floor[gcd(i,j)=1] ]

[=sum_{i=1}^{n}sum_{j=1}^{i-1}lfloorfrac{n}{i(i+j)} floor[gcd(i,j)=1] ]

根据莫比乌斯函数的性质(sum_{k|n}mu(k)=[n=1])

也就是

[=sum_{i=1}^{n}sum_{j=1}^{i-1}lfloorfrac{n}{i(i+j)} floorsum_{k|i,k|j}mu(k) ]

枚举(k)可得

[=sum_{k=1}^{n}mu(k)sum_{i=1}^{lfloorfrac{n}{k} floor}sum_{j=1}^{i-1}lfloorfrac{n}{ik(ik+jk)} floor ]

[=sum_{k=1}^{n}mu(k)sum_{i=1}^{lfloorfrac{n}{k} floor}sum_{j=1}^{i-1}lfloorfrac{lfloorfrac{n}{ik^2} floor}{i+j} floor ]

可以发现(i,j,k)的取值只能在(sqrt n)范围内,所以

[=sum_{k=1}^{sqrt{n}}mu(k)sum_{i=1}^{lfloorfrac{sqrt{n}}{k} floor}sum_{j=1}^{i-1}lfloorfrac{lfloorfrac{n}{ik^2} floor}{i+j} floor ]

时间复杂度(O(sqrt{n}log n))

代码

#include <cstdio>
#include <cmath>
#define rr register
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef unsigned uit;
const uit N=47001;
uit prime[N>>3],cnt,n;
int mu[N]; bool v[N];
inline long long answ(uit x,uit y){
    rr long long ans=0; rr uit t=x<<1;
    for(rr uit l=x+1,r;l<t;l=r+1){
        if(!(y/l)) return ans;
        r=min(y/(y/l),t-1);
        ans+=(r-l+1)*(y/l);
    }
    return ans;
}
signed main(){
    scanf("%u",&n);
    rr uit m=sqrt(n); rr long long ans=0;
    for (rr uit i=1;i<=m;++i){
        if (i>1){
            if (!v[i]) prime[++cnt]=i,mu[i]=-1;
            for (rr uit j=1;j<=cnt&&prime[j]<=m/i;++j){
                v[i*prime[j]]=1;
                if (i%prime[j]) mu[i*prime[j]]=-mu[i];
                    else break;
            }
        }else mu[i]=1;
        if (!mu[i]) continue;
        for (rr uit j=1;j*i<=m;++j)
            ans+=answ(j,n/(i*i*j))*mu[i];
    }
    printf("%lld",ans);
    return 0;
}

洛谷 6271 一个人的数论

题目

已知(f_d(n))表示所有小于(n)且与(n)互质的正整数的(d)次方的和，给出(n=prod_{i=1}^{cnt}p_i^{c_i})，和(d)，求(f_d(n)mod 1000000007)

分析

那么(f_d(n)=sum_{i=1}^ni^d*[gcd(n,i)==1])
根据莫比乌斯函数的性质(sum_{d|n}mu(d)=[n==1])
得到

[f_d(n)=sum_{i=1}^ni^d*(sum_{k|n,k|i}mu(k)) ]

[f_d(n)=sum_{k|n}sum_{i=1}^n[k|i]i^dmu(k) ]

[large f_d(n)=sum_{k|n}sum_{i=1}^{lfloorfrac{n}{k} floor}(ki)^dmu(k) ]

[f_d(n)=sum_{k|n}mu(k)k^dsum_{i=1}^{lfloorfrac{n}{k} floor}i^d ]

后面这个东西把它变成(s(n))，感性理解，是一个关于(n)的(d+1)次多项式，也就是可以表示成(sum_{i=0}^{d+1}a_in^i)，其中(a_i)可以高斯消元得到
那么

[f_d(n)=sum_{i=0}^{d+1}a_isum_{k|n}mu(k)k^d(frac{n}{k})^i ]

后面这坨变成了狄利克雷卷积，可以用积性函数解决
也就是若

[g(k)=sum_{k|n}mu(k)k^d(frac{n}{k})^i ]

把(n)质因数分解，分别求出单个质数的指数次幂的答案再相乘

[g(p^t)=sum_{j=0}^tmu(p^j)p^{dj}p^{(t-j)i} ]

因为

[egin{cases}mu(p^0)=1\ mu(p^1)=-1\mu(p^t),otherwise=0end{cases} ]

所以

[g(p^t)=p^{ti}-p^dp^{(t-1)i}=p^{ti}(1-p^{d-i}) ]

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int mod=1000000007;
int b[1011][2],a[111][111],c[111],m,n,ans;
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans;
}
inline void swap(int &a,int &b){rr int t=a;a=b,b=t;}
inline signed ksm(int x,int y){
    rr int ans=1;
    for (;y;y>>=1,x=1ll*x*x%mod)
        if (y&1) ans=1ll*ans*x%mod;
    return ans;
}
inline void init(){
    for (rr int i=0;i<m+2;++i){
        a[i][0]=1;
        for (rr int j=1;j<m+2;++j) a[i][j]=1ll*a[i][j-1]*(i+1)%mod;
        a[i][m+2]=a[i][m]+(i>0?a[i-1][m+2]:0),a[i][m+2]-=mod*(a[i][m+2]>=mod);
    }
    for (rr int i=0;i<m+2;++i){
        for (rr int j=i;j<m+2;++j) if (a[j][i])
            for (rr int k=0;k<m+3;++k) swap(a[i][k],a[j][k]);
        for (rr int j=0;j<m+2;++j) if (i!=j&&a[j][i]){
            rr int elim=1ll*a[j][i]*ksm(a[i][i],mod-2)%mod;
            for (rr int k=i;k<m+3;++k)
                a[j][k]=a[j][k]-1ll*a[i][k]*elim%mod,a[j][k]+=mod*(a[j][k]<0);
        }
    }
    for (rr int i=0;i<m+2;++i)
        c[i]=1ll*a[i][m+2]*ksm(a[i][i],mod-2)%mod;
    return;
}
signed main(){
    m=iut(); n=iut(); init();
    for (rr int i=1;i<=n;++i) b[i][0]=iut(),b[i][1]=iut();
    for (rr int i=0;i<m+2;++i){
        rr int mul=1;
        for (rr int j=1;j<=n;++j)
            mul=1ll*mul*ksm(b[j][0],1ll*b[j][1]*i%(mod-1))%mod,
            mul=1ll*mul*(mod+1-ksm(b[j][0],m-i+(mod-1)*(m<i)))%mod;
        mul=1ll*mul*c[i]%mod,ans=ans+mul-mod*(ans+mul>=mod);
    }
    return !printf("%d",ans+mod*(ans<0));
}

后续

参考于pengym的杜教筛

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Spare-No-Effort/p/13855219.html