数学 = 恐怖

莫比乌斯函数

μ\mu 为莫比乌斯函数，定义为

μ(n)={1n=10n 含有平方因子(−1)kk 为 n 的本质不同质因子个数\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases}

—— 引自 OI wiki

筛法求莫比乌斯函数

考虑 nn 最小质因数为 pp，n/p=n′n/p=n'。
若 n′ mod p=0n' \bmod p = 0, μ(n)=0\mu(n)=0。（含有平方因子）
否则，μ(n)=−μ(n′)\mu(n)=-\mu(n')。（分类讨论几种情况就能发现）

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
int mu[N],pri[N],cnt;
bool not_prime[N];

mu[1]=1; // 初始值
for(int i=2;i<N;i++){
    if(!not_prime[i])mu[i]=-1,pri[cnt++]=i; // μ(质数)=-1
    for(int j=0;j<cnt&&i*pri[j]<N;j++){
        not_prime[i*pri[j]]=1;
        if(i%pri[j]==0)break; // μ(x)=0
        mu[i*pri[j]]=-mu[i]; // 多了一个 -1
    }
}

莫比乌斯反演

∑d∣nμ(d)={1n=10n≠1\sum_{d\mid n}\mu(d)= \begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases}

即 ∑d∣nμ(d)=[n=1]\sum_{d\mid n}\mu(d)=[n=1]。

证明：n=1n=1 正确性显然。若 n>1n>1，发现 nn 的每个质因子只有一个有用。（因为多的因子带来的因数都含质数的平方，没有用），则若设 nn 有 kk 个不同的质因数，然后答案即为 ∑i=0k(ki)⋅(−1)i=0\sum_{i=0}^k \binom k i \cdot (-1)^i = 0。（枚举有 ii 个因数的项的个数）

利用这个，我们可以转化一些形为 [?=1][? = 1] 的问题。

例题

  1. 求 ∑i=1n∑j=1m[gcd⁡(i,j)=k]\displaystyle \sum _{i=1}^n\sum_{j=1}^m [\gcd(i,j)=k]。

    P3455 [POI2007] ZAP-Queries

    ∑i=1n∑j=1m[gcd⁡(i,j)=k]=∑i=1⌊n/k⌋∑j=1⌊m/k⌋[gcd⁡(i,j)=1](gcd 转化)=∑i=1⌊n/k⌋∑j=1⌊m/k⌋∑d∣gcd⁡(i,j)μ(d)(莫比乌斯反演)=∑dμ(d)∑i=1⌊n/k⌋[d∣i]∑j=1⌊m/k⌋[d∣j](交换求和顺序)=∑d=1min⁡(⌊n/k⌋,⌊m/k⌋)μ(d)⌊nkd⌋⌊mkd⌋(范围内因数个数) \begin{aligned} & \sum _{i=1}^n\sum_{j=1}^m [\gcd(i,j)=k]\\ & = \sum _{i=1}^{\lfloor n/k \rfloor}\sum_{j=1}^{\lfloor m/k \rfloor} [\gcd(i,j)=1] & \text{(gcd 转化)}\\ & = \sum _{i=1}^{\lfloor n/k \rfloor}\sum_{j=1}^{\lfloor m/k \rfloor} \sum_{d \mid \gcd(i,j)}\mu(d) & \text{(莫比乌斯反演)}\\ & = \sum_{d}\mu(d) \sum _{i=1}^{\lfloor n/k \rfloor} [d \mid i] \sum_{j=1}^{\lfloor m/k \rfloor} [d \mid j] & \text{(交换求和顺序)}\\ & = \sum_{d=1}^{\min(\lfloor n/k \rfloor,\lfloor m/k \rfloor)}\mu(d) \left\lfloor\dfrac n {kd}\right\rfloor \left\lfloor\dfrac m {kd}\right\rfloor & \text{(范围内因数个数)}\\ \end{aligned}

    至此，可以使用数论分块解决。预处理出莫比乌斯函数的前缀和即可。

    复杂度 O(n+Tn)O(n+T\sqrt n)。

    参考代码

  2. 求 ∑i=ab∑j=cd[gcd⁡(i,j)=k]\displaystyle \sum _{i=a}^b\sum_{j=c}^d [\gcd(i,j)=k]。

    P2522 [HAOI2011] Problem b

    设 f(n,m)=∑i=1n∑j=1m[gcd⁡(i,j)=k]f(n,m) =\displaystyle \sum _{i=1}^n\sum_{j=1}^m [\gcd(i,j)=k]，则原式等于 f(b,d)−f(a−1,d)−f(b,c−1)+f(a−1,c−1)f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)。（容斥原理）

    即转化为例 1。

    参考代码

  3. 求 ∑i=1n∑j=1m[gcd⁡(i,j)=质数]\displaystyle \sum _{i=1}^n\sum_{j=1}^m [\gcd(i,j)=\text{质数}]。

    P2257 YY的GCD

    多组数据，T≤104,n,m≤107T\le 10^4, n,m\le 10^7。

    ∑i=1n∑j=1m[gcd⁡(i,j)=质数]=∑p为质数∑d=1min⁡(⌊n/p⌋,⌊m/p⌋)μ(d)⌊npd⌋⌊mpd⌋=∑p为质数∑T=kp,k∈Zμ(Tp)⌊nT⌋⌊mT⌋(令 T=pd )=∑T=1⌊nT⌋⌊mT⌋∑p为质数,p∣Tμ(Tp)(交换求和顺序) \begin{aligned} & \sum _{i=1}^n\sum_{j=1}^m [\gcd(i,j)=\text{质数}] \\ & = \sum_{p\text{为质数}}\sum_{d=1}^{\min(\lfloor n/p \rfloor,\lfloor m/p \rfloor)}\mu(d) \left\lfloor\dfrac n {pd}\right\rfloor \left\lfloor\dfrac m {pd}\right\rfloor\\ & = \sum_{p\text{为质数}}\sum_{T=kp,k\in \Z}\mu\left(\dfrac T p\right) \left\lfloor\dfrac n {T}\right\rfloor \left\lfloor\dfrac m {T}\right\rfloor & (\text{令 }T=pd\ )\\ & = \sum_{T=1}\left\lfloor\dfrac n {T}\right\rfloor \left\lfloor\dfrac m {T}\right\rfloor \sum_{p\text{为质数},p \mid T}\mu\left(\dfrac T p\right)& (\text{交换求和顺序})\\ \end{aligned}

    令 f(n)=∑p为质数,p∣nμ(np)f(n) = \displaystyle\sum_{p\text{为质数}, p \mid n}\mu\left(\dfrac n p\right)。考虑在线性筛过程中求出 ff。

    设 nn 的最小质因数为 p0p_0，n′=n/p0n'=n/p_0。若n′ mod p0=0n' \bmod p_0 = 0，f(n)=μ(n′)f(n)=\mu(n')，否则 f(n)=−f(n′)+μ(n′)f(n)=-f(n')+\mu(n')。

    证明：

    1. 若 n′ mod p0=0n' \bmod p_0 = 0：

      f(n)=∑p为质数,p∣n′μ(n′p⋅p0)f(n) = \displaystyle\sum_{p\text{为质数}, p \mid n'}\mu\left(\dfrac {n'} p \cdot p_0\right)。
      求和中，当 p≠p0p\ne p_0 时，n′p⋅p0\dfrac {n'} p \cdot p_0 一定含有 p02p_0^2 作为因数，则 μ(n′p⋅p0)=0\mu\left(\dfrac {n'} p \cdot p_0\right)=0，无需计算。因此 f(n)=μ(n′p0⋅p0)=μ(n′)f(n)=\mu\left(\dfrac {n'} {p_0} \cdot p_0\right)=\mu(n')。

    2. 若 n′ mod p0≠0n' \bmod p_0 \ne 0

      f(n)=(∑p为质数,p∣n′μ(n′p⋅p0))+μ(np0)f(n) = \left( \displaystyle\sum_{p\text{为质数}, p \mid n'}\mu\left(\dfrac {n'} p \cdot p_0\right) \right)+ \mu\left(\dfrac n {p_0}\right)。

      前面的求和每一项都加入了一个新的因数，所以 μ(n′p⋅p0)=−μ(n′p)\mu\left(\dfrac {n'} p \cdot p_0\right)=-\mu\left(\dfrac {n'} p \right)。后面即为 μ(n′)\mu(n')。因此加起来就是 −f(n′)+μ(n′)-f(n')+\mu(n')。

    之后对 ff 求前缀和，然后数论分块即可。
    复杂度 O(n+Tn)O(n + T\sqrt n)。（认为 n,mn,m 同阶）

    参考代码

  4. 求 ∑i=1n∑j=1mlcm⁡(i,j)\displaystyle \sum _{i=1}^n\sum_{j=1}^m \operatorname {lcm}(i,j)。对 2010100920101009 取模。

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

    ∑i=1n∑j=1mlcm⁡(i,j)=∑i=1n∑j=1mijgcd⁡(i,j)(lcm性质)=∑d∑i=1n[d∣i]∑j=1m[d∣j]ijd(枚举 gcd)=∑dd∑i=1⌊n/i⌋∑j=1⌊m/i⌋ij[gcd⁡(i,j)=1](将i,j用i/d,j/d代换) \begin{aligned} & \sum _{i=1}^n\sum_{j=1}^m \operatorname {lcm}(i,j) \\ & = \sum _{i=1}^n\sum_{j=1}^m \dfrac{ij}{\gcd(i,j)} & \text{(lcm性质)}\\ & = \sum_{d}\sum _{i=1}^n[d\mid i] \sum_{j=1}^m [d\mid j] \dfrac{ij}d & \text{(枚举 gcd)}\\ & = \sum_{d} d \sum _{i=1}^{\lfloor n/i\rfloor} \sum_{j=1}^{\lfloor m/i\rfloor} {ij} [\gcd(i,j)=1] & \text{(将}i,j\text{用}i/d,j/d\text{代换)}\\ \end{aligned}

    令f(n,m)=∑i=1n∑j=1mij[gcd⁡(i,j)=1]=∑i=1n∑j=1mij∑d∣gcd⁡(i,j)μ(d)(莫比乌斯反演)=∑dμ(d)∑i=1n[i∣d]i∑j=1m[j∣d]j(交换求和顺序)=∑dμ(d)d2∑i=1⌊n/i⌋i∑j=1⌊m/i⌋j(将i,j用i/d,j/d代换)记g(n)=n(n+1)2,则f(n,m)=∑dμ(d)d2g(⌊n/i⌋)g(⌊m/i⌋) \begin{aligned} \text{令} f(n,m) &=\sum _{i=1}^{ n} \sum_{j=1}^{m} {ij} [\gcd(i,j)=1] \\ &=\sum _{i=1}^{ n} \sum_{j=1}^{m} {ij} \sum_{d\mid \gcd(i,j)}\mu(d) & \text{(莫比乌斯反演)} \\ &=\sum_d \mu(d) \sum _{i=1}^{ n} [i\mid d]i \sum_{j=1}^{m} [j\mid d]{j} & \text{(交换求和顺序)} \\ &=\sum_d \mu(d)d^2 \sum _{i=1}^{\lfloor n/i\rfloor} i \sum_{j=1}^{\lfloor m/i\rfloor} {j} & \text{(将}i,j\text{用}i/d,j/d\text{代换)} \\ \text{记} g(n)&=\dfrac{n(n+1)}2 ,\\ \text{则} f(n,m)&=\sum_d \mu(d)d^2 g(\lfloor n/i\rfloor)g(\lfloor m/i\rfloor) \end{aligned}

    则 f(n,m)f(n,m) 可以采用数论分块求出。则原式可再套一层数论分块求出。

    参考代码