noone___'s blog
0%

莫比乌斯反演

发表于 更新于 分类于
莫反+杜教筛

暂停更新，遇见再更

闲下来取写题单

某些前置知识

整除分块

  • qwq

    众所周知

    $a\%b=a-b*\left\lfloor \frac{a}{b} \right\rfloor$

  • 规定：

    当前块的左端点 $l$，块值 $k$，右端点 $r$

  • 用途：

    快速处理形如

    的式子

  • 用法：

    代入一个 $n$ 可发现某些 $\left\lfloor \frac{n}{i} \right\rfloor$ 的值相同且呈块状分布

    对于一个起始下标为 $l$ 的块，其终止下标为 $\left\lfloor \frac{n}{\left\lfloor \frac{n}{l} \right\rfloor} \right\rfloor$

  • 证明：

    对于该块中的每个数 $i$，有 $k=\left\lfloor \frac{n}{i} \right\rfloor=\left\lfloor \frac{n}{l} \right\rfloor$

    即 $ik \leq n$

    所以要找到使 $ik \leq n$ 成立的最大值

    所以得到：

    推导得 $r=\left\lfloor \frac{n}{k} \right\rfloor = \left\lfloor \frac{n}{\left\lfloor \frac{n}{l} \right\rfloor} \right\rfloor$

  • 例题

    P2261 [CQOI2007]余数求和

    1
    2
    3
    4
    5
    6
    7
    8
    ans=n*k;
    for(ll l=1,r;l<=n;l=r+1){
        if(k/l)
            r=min(n,k/(k/l));
        else
            r=n;
        ans-=( (r-l+1)*(l+r)/2 /*等差数列*/) *(k/l)/*块值*/;
    }

  • 拓展

    • 例1

      • [一]

  • [二]通法

  • 例2

    $求\sum^n_{i=1} \left\lfloor \frac{n}{i^2} \right\rfloor$

    • 按通法推导

      令$r^*=r^2$

  • 例3

    • 求 $\sum^n_{i=1} \left\lceil \frac{n}{i} \right\rceil$

      转化：加上 $\frac{i-1}{i}$ 即可

      问题转化为

  • 例题

    • CF830C Bamboo Partition

      求：$\sum^n_{i=1} d-((a_i-1)\%d+1) \leq k$

      解：

      $\therefore$ 右边定值，枚举左边

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    for(rei ll l=1,r;l<=MAX;l=r+1){//暴力试每一个块
    //把l看成是d
        r=1e18;
        ll sum=0;
        for(rei i=1;i<=n;++i)
            if(a[i]-1>=l){//每一个 ⌊a[i]-1/d⌋ 有值
                sum+=(a[i]-1)/l;
                r=min(r,(a[i]-1)/((a[i]-1)/l));
            }
        ll tmp=k/(sum+n);//见blog的式子推导
        if(l<=tmp) ans=max(ans,min(tmp,r));
    }
    if(MAX < k/n) ans=max(ans,(ll)k/n);

    • P2260 [清华集训2012]模积和

      考虑一个容斥：$原式=(忽略i\not=j 条件时的值)-(i=j时原式的值)$

      • 忽略 $i\not=j$时：

        这与[余数求和]相似

      • $i=j$

积性函数

  • 定义

    积性函数 $f(x)$ 满足 $f(1)=1$ 且 $\forall x,y\in \mathbb{N}_{+},\gcd(x,y)=1$ 都有 $f(xy)=f(x)f(y)$

  • 常见形式

    • 单位元 $\epsilon(n)=[n=1]$

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

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

  • 性质

迪利克雷卷积

  • 注：

    $\sum_{d \mid n}$ 表示对 $n$ 的所有正因子求和

  • 定义

    定义数论函数的迪利克雷卷积为 $h=f \circ g$ ,其中

    注：定义卷积符号为 $\circ$

    原因戳我 好看

  • 性质

    • 迪利克雷卷积拥有交换律，分配律，结合律

    • 单位元 (也记作 $\varepsilon$ )

      函数 $I(n)=[n=1]$

      易知:

    • 逆元 (当且仅当 $f(1) \neq 0$)

      若 $f \circ g=I$，则称 $g(x)$ 是 $f(x)$ 的逆元

      可以构造：

欧拉函数

  • 定义

    $\varphi(n) \ =\ n*\prod^n_{i=1} \left( 1-\frac{1}{p_i}\right)$

    其中 $p_i$ 是 $n$ 的质因数

    即小于等于 $n$ 且与 $n$ 互素的数的个数

  • 性质

    • $1.$ 是积性函数

    • $2.$

      对于质数 $p$

      $\varphi(p)=p-1$

    • $3.$

      若 $n=p^k$ ,其中 $p$ 是质数

      $\varphi(n)\ =\ p^k-p^{k-1}\ =\ (p-1)p^{k-1}$

      证：$1$ 到 $n$ 中除了 $p$ 的倍数，都与 $p^k$ 互质，且 $1$ 到 $n$ 中 $p$ 的倍数的个数为 $\displaystyle{\frac{p^k}{p}}=p^{k-1}$

    • $4.$

      所有小于等于 $n$ 且与 $n$ 互质的数的个数和 $sum=n*\displaystyle{\frac{\varphi(n)}{2}}$

      证：用反证法可知：

      若 $\gcd(n,i)=1$，则 $\gcd(n,n-i)=1$ $\Rightarrow$ 更相减损术

      所以每个与 $n$ 互质的数都是成对的

      $i$ 与 $n-i$ 成对

    • $5.$

      若 $i\mid p$，其中 $p$ 是质数

      则 $\varphi(i\cdot p)=p\cdot \varphi(i)$

      否则 $\varphi(i*p)=(p-1)\varphi(i)$

      即

      证明咕咕咕

    • $6.欧拉反演$

      $\displaystyle{\sum_{d\mid n}\varphi(d)=n}$

      • 证：

      • 扩展：

    • $7. \varphi 与 \mu$

      $\displaystyle{\frac{\varphi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d}}$

      • 证：

        同除 $n$得：

写在前面的总结

遇到艾弗森方程，转化为$\sum_{d\mid n} \mu(d)$

遇到具体的值，考虑欧拉函数 ————by CTime_Pup_314

  • 当遇到迪利克雷卷积形式的式子($\sum_{d\mid n}···$)时

    看标准分解式 $p_1^{a_1}p_2^{a_2}…p_n^{a_n}$

    并分析其中一个 $p_i^{a_i}$

  • 再尝试转化出 $F(n)=\sum_{d\mid n}\mu(\frac{n}{d}) f(d)$ 的形式

    再考虑加入 $p$ 的影响:

    分为 $n \perp p$ 和 $n\not\perp p$两种讨论

    • $n \perp p$ 时，$\sum_{d\mid n}\mu\left(\frac{np}{d}\right) f(d) + \sum_{d\mid n}\mu\left(\frac{np}{dp}\right)f(dp)\ =\ -F(n)+\mu(n)$

    • $n \not\perp p$ 时，$\sum_{d\mid n}\mu\left(\frac{np}{d}\right) f(d) + \sum_{d\mid n}\mu\left(\frac{np}{dp}\right) f(dp)\ =\ \mu(n)$

  • 若问题类似与 $\displaystyle{\sum_{i=1}^n\sum_{j=1}^mf\left(gcd(i,\ j)\right )}$

    则转化为 $\displaystyle{\sum_{T=1}^n\left\lfloor \frac{n}{T} \right\rfloor \left\lfloor \frac{m}{T} \right\rfloor \sum_{d\mid T}\mu\left(\frac{T}{d}\right)f(d)}$

莫比乌斯函数

  • 定义

    设 $n=\prod_{i=1}^k p_i^{c_i}$，其中 $p_i$ 为质因子, $c_i$ 为个数

  • 性质

    • 证明

      显然不用考虑使 $\mu(d)=0$ 的那些 $d$

      设 $n$ 有 $k$ 个互异质因数

      $\therefore$ 由 $r$ 个质因数乘起来的因数 $d$ 有 $C_k^r$ 个

      由二项式定理：

      可知

      取 $x=-1,y=1$

      同时，这也证明了$\sum_{d \mid n} \mu(d)=[n=1]= \varepsilon(n)$

      以及 $\mu \circ 1=\varepsilon$

    • 性质2

      和上面的一模一样。。。

  • 线性筛求法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int p[N];//第tot个质因数值

inline void init(){
    mu[1]=1;
    for(rei i=2;i<=n;++i){
        if(!flg[i])/*之前没有用过该质因数*/ p[++tot]=i,mu[i]=-1;
        for(rei j=1;j<=tot && i*p[j]<=n ;++j){
            flg[ i*p[j] ]=1;//每个质因数的倍数打上标记
            if(!(i%p[j])){//有平方因子
                mu[ i*p[j] ]=0;
                break;
            }
            mu[ i*p[j] ]=-mu[i];
        }
    }
}

莫比乌斯反演

  • 公式

  • 略证

好吧我不怎么会证

用莫比乌斯函数就可以解决大部分莫反问题——by CTime_Pup_314

需要带脑子推式子的例题

  • k倍经验

    UVA11417 GCD垃圾红题，UVA11424 GCD - Extreme (I)，P1390 公约数的和，P2398 GCD SUM，P2568 GCD，SP3871 GCDEX - GCD Extreme，UVA11426 拿行李（极限版），SP3871 GCDEX - GCD Extreme,[SP19985]GCDEX2 - GCD Extreme (hard)（要用杜教筛）， [SDOI2008] 仪仗队

请仔细留意如何筛出所需函数

  • 附线性筛板子 不压行显得多一点 改码风了，不压行好烦

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //f是你想要的函数
    inline void init(){
        mu[1]=1,varphi[1]=1,f[1]=1;
        for(rei d=2;d<N;++d){
            if(!flag[d]){
                prime[++tot]=d,varphi[d]=d-1,mu[i]=-1;
            }
            f[d]=它该等于的式子
            for(rei j=1;j<=tot && d*prime[j]<N;++j){
                rei tmp=d*prime[j]; flag[tmp]=1;
                varphi[tmp]=varphi[d] * (d%prime[j]/*是否互素*/ ? prime[j]-1 : prime[j]);
               	(!(d%p[j])) ? mu[d*p[j]]=0 : mu[d*p[j]]=-mu[i];
            }
            这里可能需要进一步处理f(n)
        }
        这里也有可能
    }

注：规定所有的 $n<m$ , 所有出现的 $p$ 为质数

  • $1$

    P4450 双亲数

    解：

  • $2$

    P2522 [HAOI2011]Problem b

    解：

    将范围缩小 $k$ 就可以

    即

  • $3$

  • $4$

    P1447 [NOI2010] 能量采集

    由题，没有被遮挡的植物坐标 $(x,y)$ 满足 $n\perp m$，而一条线 $(0,0)-(x,y)$ 上被挡住的植物有 $\gcd(x,y)-1$ 个

    先进行简单化简

    设 $T=kd$

    设 $\operatorname{F}(n)=\sum_{d\mid n}\mu \left( \frac{n}{d} \right)d$

    根据上面的总结可知

    当 $n\perp p$ 时，

    当 $n\not\perp p$ 时，

    $\therefore 显然F(n)符合欧拉函数的性质$

    • 变式

      P4449 于神之怒加强版

      先把 $k$ 提出来得

      处理 $\sum_{d\mid T}\mu \left( \frac{T}{d} \right)d^k$

      设积性函数 $f(T)=id^k \circ \mu$

      当 $x=1$

      当 $x>1$

      $\therefore$ 筛法为

    • 变式

      UVA11424 GCD - Extreme (I)

      有一个比莫反更好的方法

      设 $f(n)=\gcd(1,n)+\gcd(2,n)+…+\gcd(n-1,n)$

      $\therefore ans=f(2)+f(3)+…+f(n)$

      设 $g(n,x)$ 表示 $\gcd(x,n)=i$ 的小于 $n$ 的正整数个数

      考虑 $\varphi$ 即可

      精神不稳就这吧

      我的精神是正常的只是懒得写

  • $5$

    P2257 YY的GCD

    推导与上一题类似，略(懒)

  • $6$

    SP5971 LCMSUM - LCM Sum

    • [ 法一 ]

      $\gcd(i,n)$ 值相同的放在一起 $\Rightarrow$ 统计 $\gcd(i,n)=d$ 的个数

      当 $\gcd(i,n)=d$ , $\gcd(\frac{i}{d},\frac{i}{n})=1$

      所以 $\gcd(i,n)=d$ 的个数有 $\varphi\left(\frac{n}{d}\right)$

    • [ 法二 ]

      提出式子 $\displaystyle{\sum_{i=1}^n [\ \gcd(i,n)=1\ ]\cdot i}$

      式子的含义是求小于等于 $n$ 的数中与 $n$ 互质的数的和

      这与上文推导的欧拉函数性质 $4$ 一样

      即 $sum=n*\displaystyle{\frac{\varphi(n)}{2}}$

  • $7.$

    P3327 [SDOI2015]约数个数和

    设 $\operatorname{d}(i)$ 为 $i$ 的约数个数 ，注意仍有 $n<m$

    有一个显然的结论:$\displaystyle{\operatorname{d}(n)=\sum_{x\mid n,y\mid n}[ \ \gcd(x,y)=1 \ ]}$

    然而 $d$ 在分母上，不易打表，无法数论分块 $\Rightarrow$ 重新考虑 $(1)$ 式

    $(1)$ 中对每组 $(d,i,j)$ ，先考虑 $\displaystyle{\sum_{i=1}^n \sum_{j=1}^m \sum_{x\mid i} \sum_{y\mid j}}$ $(2)$

    其贡献为 $\left(i的因数(x)的个数 \left(即\sum_{x\mid i} \right) \right) \cdot \left(j的因数的个数 \left(即\sum_{y\mid j} \right) \right)$

    再提前 $\displaystyle{\sum_{d\mid \gcd(x,y)}\mu(d)}$ ，转化为从 $1$ 到 $n$ 枚举 $d$ ，同时缩小 $(2)$ 式的数据范围

    若使 $[\ d\mid \gcd(x,y) \ ]=1$ ，那么 $x,y$ 都为 $d$ 的倍数 ，所以数据范围应为枚举 $d,2d,3d,4d…$ 直至 $kd>n$

    式子含义明显

    设 $\displaystyle{\operatorname{f}(i)=\sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor}$ ，考虑对 $\operatorname{f}(i)$ 分块

    显然有 $\displaystyle{\operatorname{f}(i)=\sum_{i=1}^n} \operatorname{d}(x)$

  • $8$

    P1829 【[国家集训队]Crash的数字表格 / JZPTAB】

    设 $S(n)=\sum_{i=1}^n=\frac{n(n+1)}{2}$

    再设 $T=kd$

    $\therefore$ 只需预处理 $\sum_{d\mid T}Td\mu(d)$ 即可

    传送门

  • $9.$

    P3911 最小公倍数之和

    考虑转化该式：

    设 $\displaystyle{M=\max_{1<=i<=n}A_i \quad,\quad C_i=\sum_{d=1}^n [A_d=i] }$

    其余按套路来

    考虑后面部分的 $C$ 如何快速处理

    设 $T=dk$

    简单的变式AT5200 [AGC038C] LCMs

    求 $\displaystyle{\sum_{i=0}^{n}\sum_{j=i+1}^{n}\text{lcm}(A_i,A_j)} \quad \mod p$

    注意及时取模即可

  • $10.$

    P3768 简单的数学题

    • 前半部分

      杜教筛 $\Rightarrow$ 设 $S(n)=\sum_{d=1}^n \varphi(d) * d^2$

      若使 $f\circ g$ 结果只有 $n$ $\Rightarrow$ 取 $g=id$

    • 右半部分

      求 $\displaystyle{\left(\sum_{i=1}^ni\right)^2}$

      然而我只会证明$\displaystyle{\left(\sum_{i=1}^ni\right)^2=\sum_{i=1}^n i^3 }$

      最快的方法是差分

      设 $\displaystyle{A_n=\sum_{i=1}^n i^3 \ , \ B_n=\sum_{i=1}^n i}$

      一).

      二).

  • 11.

    P1587 [NOI2016] 循环之美

    一个神仙转化如下

    设该纯循环小数的循环节长度为 $times$，$\left\{\frac{x}{y}\right\}$ 表示 $\frac{x}{y}$ 的小数部分

    在 $k$ 进制下，总有 $\displaystyle{\left\{\frac{x}{y} \right\} = \left\{\frac{x \cdot k^{times}}{y} \right\} }$

    即

    考虑到最简分数，即 $\gcd(x,y)=1$

    $\therefore$ 问题转化为

    最后对 $k=1$ 的情况直接算即可

  • 12.

    P3704 [SDOI2017]数字表格

    设 $n<m$

    看指数项发现是HAOI2011

    $\sout{好了可以O(nT)了}$

    用能量采集的 $\text{trick}$ 提出 $T=kd$ ,即

    $T$ 对 $d$ 取值做出了限制条件 $\Rightarrow$ 考虑把 $T$ 提到式子最前面,即

    即

要带更多的脑子

+数据结构

  • $1.$

    P3312 [SDOI2014]数表

    给定 $A$ , 求 $\displaystyle{\sum_{i=1}^n \sum_{j=1}^m d( \ \gcd(i,j) \ ) [ \ d( \ (\gcd(i,j) \ ) \leq A \ ]}$

    众所周知 $d(n)$ 代表约数的和

    $设 \displaystyle{f(i)=\sum_{x\mid T}\mu(x) * d\left( \frac{T}{x} \right) \left[ d\left(\frac{T}{x} \right) \leq A \right]}$

    看起来是关于 $(T,A)$

    将询问按 $A$ 升序排列并提前处理 $d(x)$

    当 $A$ 增大时，该函数值也以一定规律增大 $\Rightarrow$ 看成插入

    $\therefore$ 需要支持插入与查询的数据结构 $\Rightarrow$ 树状数组

    每次暴力加入所有 $d(x) \leq A$ 的 $x$

    即对所有 $kx\leq n$ 都有 $f(kx)+=d(xyt4)\mu(k)$

+记忆化

  • $1.$

    P4619 [SDOI2018]旧试题

    求

    首先可以回忆起 P3327 [SDOI2015]约数个数和 这道题中对 $d(xy)$ 的处理方法： $d(i\times j)=\sum_{x\mid i}\sum_{y\mid j} [\gcd(x,y)=1]$

    所以在该题中，对于每两个数都有以上关系式

考虑记忆化搜索(指暴力)

设 $f_{i,A,B,C}$ 表示对于所有满足 $(u,v) ; (u,w) ; (v,w)$ 的所有公共素因子不小于第 $i$ 个素数 $p_i$ 时 $\left\lfloor \frac{a}{u} \right\rfloor \left\lfloor \frac{b}{v} \right\rfloor \left\lfloor \frac{c}{w} \right\rfloor$ 的求和

考虑转移：分为三组，两两考虑，以 $(u,v)$ 为例：

对于 $f_{i-1,A,B,C}$ 可以分成两组：

- $(u,v)$ 的公共素因子均不小于 $p_i$ ，我们需要的是这部分

- $(u,v)$ 的公共素因子有 $p_{i-1}$ ，这部分需要被减去，即减去

$(u,w) , (v,w)$ 同理

注意 $p_{i-1}\mid(u,v,w)$ 的情况被计算 $3$ 次，所以最后应该加上

杜教筛

  • 用途：求积性函数 $\operatorname{f}(n)$ 的前缀和，即 $\sum_{i=1}^n f(i)$，其时间复杂度低于线性

  • 方法：

    $f(i)$ 为已知的函数

    设 $S(n)=\sum f(i)$

    出于前缀和的考虑，自行选取函数 $g(n)$ ，最好使 $f\circ g$ 的式子中没有除 $n$ 以外的变量

    带入公式

  • 推导

    设函数 $S(n)=\sum_{i=1}^n f(i)$

    要计算出 $S(n)$ 关于 $S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$ 的递推式才能使复杂度低于线性

    设 $S(n)=\sum_{i=1}^n f(i)$

    任取一数论函数 $\operatorname{g}$ 均有:

    提取出 $i=1$ 时的 $g(1)S(n)$

    注：如果g是积性函数，g(1)=1

  • $\mu$ 的前缀和

    $设\operatorname{g}=I$

    I是恒等函数, 见积性函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    ll get_mu(ll x){
        if(x<MAX) return sum_mu[x];//直接线性筛
        if(mp_mu[x]) return mp_mu[x];
        ll ans=1;
        for(ll l=1,r;l<=x;l=r+1){
            r=x/(x/l);
            ans-=get_mu(x/l)*(r-l+1);
        }
        return mp_mu[x]=ans;
    }

  • $\varphi$ 的前缀和

    直接套到杜教筛公式得：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    inline void init(){
        vis[0]=vis[1]=1;
        mu[1]=phi[1]=1;
        for(rei i=2;i<N;++i){
            if(!vis[i]){
                p[++tot]=i;
                mu[i]=-1;
                phi[i]=i-1;
            }
            for(ll j=1;j<=tot && i*p[j]<N;++j){
                rei tmp=i*p[j];
                vis[tmp]=1;
                if(i%p[j]){
                    mu[tmp]=-mu[i];
                    phi[tmp]=phi[i]*phi[ p[j] ];
                }
                else{
                    mu[tmp]=0;
                    phi[tmp]=phi[i]*p[j];
                    break;
                }
            }
        }
        for(rei i=1;i<N;++i){
            mu[i]+=mu[i-1];
            phi[i]+=phi[i-1];
        }
    }

    ll getmu(int x){
        if(x<N) return mu[x];
        if(summu[x]) return summu[x];
        ll ans=1;
        for(ll l=2,r;l<=(ll)x;l=r+1){
            r=x/(x/l);
            ans-=1ll*(r-l+1)*getmu(x/l);
        }
        return summu[x]=ans;
    }

    ll getphi(int x){
        if(x<N) return phi[x];
        if(sumphi[x]) return sumphi[x];
        ll ans=1ll*x*(x+1)/2;
        for(ll l=2,r;l<=(ll)x;l=r+1){
            r=x/(x/l);
            ans-=1ll*(r-l+1)*getphi(x/l);
        }
        return sumphi[x]=ans;
    }