积性函数的各种处理(等待重构!)

    积性函数的各种处理(等待重构!)

    1:整除

    1.1:整除的性质 1

    对于 ∀a,b,c∈Z\forall a, b, c \in \mathbb{Z},有:

    ⌊abc⌋=⌊⌊ab⌋c⌋\left\lfloor \frac{a}{bc} \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{a}{b} \right\rfloor}{c} \right\rfloor

    证明

    设 ab=⌊ab⌋+r\frac{a}{b} = \left\lfloor \frac{a}{b} \right\rfloor + r,其中 0≤r<10 \leq r < 1,则:

    ⌊abc⌋=⌊ab⋅1c⌋=⌊1c(⌊ab⌋+r)⌋=⌊⌊ab⌋c+rc⌋=⌊⌊ab⌋c⌋\left\lfloor \frac{a}{bc} \right\rfloor = \left\lfloor \frac{a}{b} \cdot \frac{1}{c} \right\rfloor = \left\lfloor \frac{1}{c}\left( \left\lfloor \frac{a}{b} \right\rfloor + r \right) \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{a}{b} \right\rfloor}{c} + \frac{r}{c} \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{a}{b} \right\rfloor}{c} \right\rfloor

    Q.E.D

    1.2:整除的性质 2

    给出一个正整数 nn,对于正整数 d(1≤d≤n)d(1 \leq d \leq n),⌊nd⌋\left\lfloor \frac{n}{d} \right\rfloor 的取值不超过 2n2\sqrt{n} 种。

    证明

    可以分类讨论:

    • 若 d≤nd \leq \sqrt{n},因为 dd 的取值不超过 n\sqrt{n} 种,显然 ⌊nd⌋\left\lfloor \frac{n}{d} \right\rfloor 的取值不超过 n\sqrt{n} 种。
    • 若 d>nd > \sqrt{n},则 ⌊nd⌋≤n\left\lfloor \frac{n}{d} \right\rfloor \leq \sqrt{n},故 ⌊nd⌋\left\lfloor \frac{n}{d} \right\rfloor 的取值不超过 n\sqrt{n} 种。

    综上所述,⌊nd⌋\left\lfloor \frac{n}{d} \right\rfloor 的取值不超过 2n2\sqrt{n} 种,Q.E.D

    1.3:整除分块

    给出一个正整数 nn,请你求出:

    ∑i=1n⌊ni⌋\sum\limits_{i = 1}^n \left\lfloor \frac{n}{i} \right\rfloor

    其中 1≤n≤1091 \leq n \leq 10^9。

    分析

    观察到函数 f(x)=nxf(x) = \frac{n}{x} 在区间 (0,+∞)(0, +\infty) 上单调递减。

    所以,对于函数 g(x)=⌊nx⌋g(x) = \left\lfloor \frac{n}{x} \right\rfloor 的任意一个函数值,令 g(x)g(x) 取到该值的所有自变量 xx 组成一段连续的区间。

    根据「1.2:引理 2」,我们知道这样的区间个数也是 O(n)\mathcal{O}(\sqrt{n}) 级别的。

    对于一段满足 g(x)g(x) 均相等的区间,我们可以直接得出该区间里的所有 xx 对答案的贡献。那现在的关键在于如何得到这些区间。

    考虑任意一个 i(1≤i≤n)i(1 \leq i \leq n),我们现在要找到一个最大的 j(i≤j≤n)j(i \leq j \leq n),使得 ⌊ni⌋=⌊nj⌋\left\lfloor \frac{n}{i} \right\rfloor = \left\lfloor \frac{n}{j} \right\rfloor。结论:j=⌊n⌊ni⌋⌋j = \left\lfloor \frac{n}{ \left\lfloor \frac{n}{i} \right\rfloor } \right\rfloor。

    证明

    1. 第一步,证明其合法性(i≤j≤ni \leq j \leq n)。
    ⌊ni⌋≤ni  ⟹  ⌊n⌊ni⌋⌋≥⌊nni⌋=i  ⟹  i≤⌊n⌊ni⌋⌋=j\begin{aligned} \left\lfloor \frac{n}{i} \right\rfloor \leq \frac{n}{i} & \implies \left\lfloor \frac{n}{\left\lfloor \frac{n}{i} \right\rfloor} \right\rfloor \geq \left\lfloor \frac{n}{\frac{n}{i}} \right\rfloor = i \\ & \implies i \leq \left\lfloor \frac{n}{\left\lfloor \frac{n}{i} \right\rfloor} \right\rfloor = j \end{aligned}
    1. 第二步,证明其为最大值。

    考虑任意一个满足 ⌊ni⌋=⌊nj⌋\left\lfloor \frac{n}{i} \right\rfloor = \left\lfloor \frac{n}{j} \right\rfloor 的 jj:

    ⌊ni⌋=⌊nj⌋  ⟹  ⌊ni⌋≤nj<⌊ni⌋+1  ⟹  1⌊ni⌋+1<jn≤1⌊ni⌋  ⟹  n⌊ni⌋+1<j≤n⌊ni⌋\begin{aligned} \left\lfloor \frac{n}{i} \right\rfloor = \left\lfloor \frac{n}{j} \right\rfloor & \implies \left\lfloor \frac{n}{i} \right\rfloor \leq \frac{n}{j} < \left\lfloor \frac{n}{i} \right\rfloor + 1 \\ & \implies \frac{1}{\left\lfloor \frac{n}{i} \right\rfloor + 1} < \frac{j}{n} \leq \frac{1}{\left\lfloor \frac{n}{i} \right\rfloor} \\ & \implies \frac{n}{\left\lfloor \frac{n}{i} \right\rfloor + 1} < j \leq \frac{n}{\left\lfloor \frac{n}{i} \right\rfloor} \end{aligned}

    因为 j∈Zj \in \mathbb{Z},故 jmax⁡=⌊n⌊ni⌋⌋j_{\max} = \left\lfloor \frac{n}{ \left\lfloor \frac{n}{i} \right\rfloor } \right\rfloor。

    Q.E.D

    实现

    根据上述结论,我们就有了找出这 O(n)\mathcal{O}(\sqrt{n}) 个区间的方法。直接套结论做即可,时间复杂度是 O(n)\mathcal{O(\sqrt{n})} 的。

    for (int x = 1, nx; x <= n; x = nx + 1) {
        nx = n / (n / x);
        ans += 1ll * (nx - x + 1) * (n / x); 
    }

    1.4:多维整除分块

    给出两个正整数 n,mn, m,请你求出:

    ∑i=1min⁡(n,m)⌊ni⌋⌊mi⌋\sum\limits_{i = 1}^{\min(n, m)} \left\lfloor \frac{n}{i} \right\rfloor \left\lfloor \frac{m}{i} \right\rfloor

    其中 1≤n,m≤1091 \leq n, m \leq 10^9。

    分析

    上式的乘积项包含两个取整分式。

    考虑任意一个 ii,我们现在要找到一个最大的 jj,使得 ⌊ni⌋=⌊nj⌋\left\lfloor \frac{n}{i} \right\rfloor = \left\lfloor \frac{n}{j} \right\rfloor 且 ⌊mi⌋=⌊mj⌋\left\lfloor \frac{m}{i} \right\rfloor = \left\lfloor \frac{m}{j} \right\rfloor。易证:j=min⁡{⌊n⌊ni⌋⌋,⌊m⌊mi⌋⌋}j = \min\left\{\left\lfloor \frac{n}{ \left\lfloor \frac{n}{i} \right\rfloor } \right\rfloor, \left\lfloor \frac{m}{ \left\lfloor \frac{m}{i} \right\rfloor } \right\rfloor\right\}。

    扩展到多维也是一样的道理。

    2:积性函数

    2.1:积性函数的定义

    若数论函数 f(n)f(n) 满足:对于任意互质正整数 x,yx, y,都有 f(xy)=f(x)f(y)f(xy) = f(x)f(y)。则 f(n)f(n) 为积性函数。

    若数论函数 f(n)f(n) 满足:对于任意正整数 x,yx, y,都有 f(xy)=f(x)f(y)f(xy) = f(x)f(y)。则 f(n)f(n) 为完全积性函数。

    2.2:积性函数的简单性质

    • 对于任意积性函数 f(x)f(x),都有 f(1)=1f(1) = 1。
    • 对于任意积性函数 f(x),g(x)f(x), g(x),则以下的 h(x)h(x) 也均为积性函数:
    h(x)=f(xp)h(x)=fp(x)h(x)=f(x)g(x)h(x)=∑d∣xf(d)g(xd)\begin{aligned}h(x) & = f(x^p) \\h(x) & = f^p(x) \\h(x) & = f(x)g(x) \\h(x) & = \sum\limits_{d | x} f(d)g\left(\frac{x}{d}\right)\end{aligned}
    • 将 xx 分解质因数,若 f(x)f(x) 为积性函数,则 f(x)=∏i=1mf(pici)f(x) = \prod\limits_{i = 1}^m f(p_i^{c_i})。

    2.3:常见积性函数

    • 单位函数(完全积性):
    ϵ(n)=[n=1]\epsilon(n) = [n = 1]
    • 恒等函数(完全积性):
    IDk(n)=nk\text{ID}_k(n) = n^k
    • 常数函数(完全积性):
    1(n)=11(n) = 1
    • 约数函数(积性):
    σk(n)=∑d∣ndk\sigma_k(n) = \sum\limits_{d | n} d^k
    • 欧拉函数(积性):
    φ(n)=n∏i=1m(1−1pi)\varphi(n) = n \prod\limits_{i = 1}^m \left(1 - \frac{1}{p_i}\right)
    • 莫比乌斯函数(积性):
    μ(n)={0∃i∈[1,m],ci>11m≡0(mod2),∀i∈[1,m],ci=1−1m≡1(mod2),∀i∈[1,m],ci=1\mu(n) = \begin{cases} 0 & \exists i \in [1, m], c_i > 1 \\ 1 & m \equiv 0 \pmod 2, \forall i\in[1, m], c_i = 1 \\ -1 & m \equiv 1 \pmod 2, \forall i \in [1, m], c_i = 1 \end{cases}

    3:Dirichlet 卷积

    3.1:Dirichlet 卷积的定义

    定义两个数论函数 f,gf, g 的 Dirichlet 卷积为:

    (f∗g)(n)=∑d∣nf(d)⋅g(nd)(f \ast g)(n) = \sum\limits_{d | n} f(d) \cdot g(\frac{n}{d})

    3.2:Dirichlet 卷积的性质

    • 交换律:f∗g=g∗ff \ast g = g \ast f。
    • 结合律:(f∗g)∗h=f∗(g∗h)(f \ast g) \ast h = f \ast (g \ast h)。
    • 分配律:f∗(g+h)=f∗g+f∗hf \ast (g + h) = f \ast g + f \ast h。
    • 单位元:f∗ϵ=ff \ast \epsilon = f,因此 ϵ\epsilon 也被叫做 Dirichlet 卷积单位元。

    3.3:常见 Dirichlet 卷积式

    3.3.1:式 1

    ϵ=μ∗1  ⟺  ∑d∣nμ(d)=ϵ(n)\epsilon = \mu \ast 1 \iff \sum\limits_{d | n} \mu(d) = \epsilon(n)

    证明

    不难看出关于 nn 的函数 f(n)=∑d∣nμ(d)f(n) = \sum\limits_{d \mid n} \mu(d) 是个积性函数。

    • 当 n=1n = 1 时,显然有 f(1)=1f(1) = 1。

    • 当 n>1n > 1 时,将 nn 质因数分解,得:

    f(n)=∏i=1mf(pici)=∏i=1m(∑d∣piciμ(d))=∏i=1m(∑j=0ciμ(pij))=∏i=1m(μ(1)+μ(pi))=0\begin{aligned}f(n) & = \prod\limits_{i = 1}^m f(p_i^{c_i}) \\& = \prod\limits_{i = 1}^m \left( \sum\limits_{d | p_i^{c_i}} \mu(d) \right) \\& = \prod\limits_{i = 1}^m \left( \sum\limits_{j = 0}^{c_i} \mu(p_i^j) \right) \\& = \prod\limits_{i = 1}^m \left( \mu(1) + \mu(p_i) \right) \\& = 0\end{aligned}

    综上所述,f(n)=∑d∣nμ(d)=[n=1]f(n) = \sum\limits_{d | n} \mu(d) = [n = 1],Q.E.D

    3.3.2:式 2

    ID=φ∗1  ⟺  ∑d∣nφ(d)=n\text{ID} = \varphi \ast 1 \iff \sum\limits_{d | n} \varphi(d) = n

    证明

    不难看出关于 nn 的函数 f(n)=∑d∣nφ(d)f(n) = \sum\limits_{d | n} \varphi(d) 是个积性函数。

    • 当 n=1n = 1 时,显然有 f(1)=1f(1) = 1。
    • 当 n>1n > 1 时,将 nn 质因数分解,得:
    f(n)=∏i=1mf(pici)=∏i=1m(∑d∣piciφ(d))=∏i=1m(∑j=0ciφ(pij))=∏i=1m(1+∑j=1ciφ(pij))=∏i=1m(1+∑j=1ci(pij−pij−1))=∏i=1mpici=n\begin{aligned}f(n) & = \prod\limits_{i = 1}^m f(p_i^{c_i}) \\& = \prod\limits_{i = 1}^m \left( \sum\limits_{d | p_i^{c_i}} \varphi(d) \right) \\& = \prod\limits_{i = 1}^m \left( \sum\limits_{j = 0}^{c_i} \varphi(p_i^j) \right) \\& = \prod\limits_{i = 1}^m \left( 1 + \sum\limits_{j = 1}^{c_i} \varphi(p_i^j) \right) \\& = \prod\limits_{i = 1}^m \left( 1 + \sum\limits_{j = 1}^{c_i} \left( p_i^j - p_i^{j - 1} \right) \right) \\& = \prod\limits_{i = 1}^m p_i^{c_i} \\& = n\end{aligned}

    综上所述,f(n)=∑d∣nφ(d)=nf(n) = \sum\limits_{d | n} \varphi(d) = n,Q.E.D

    3.3.3:式 3

    φ=μ∗ID  ⟺  φ(n)=∑d∣nd⋅μ(nd)\varphi = \mu \ast \text{ID} \iff \varphi(n) = \sum\limits_{d | n} d \cdot \mu(\frac{n}{d})

    证明

    φ∗1=ID  ⟹  φ∗1∗μ=μ∗ID  ⟹  φ∗ϵ=μ∗ID  ⟹  φ=μ∗ID\begin{aligned}\varphi \ast 1 = \text{ID} & \implies \varphi \ast 1 \ast \mu = \mu \ast \text{ID} \\& \implies \varphi \ast \epsilon = \mu \ast \text{ID} \\& \implies \varphi = \mu \ast \text{ID}\end{aligned}

    Q.E.D

    4:线性筛

    线性筛,也叫 Euler 筛。可以在线性时间内筛出 1∼n1 \sim n 里的所有质数。相信大家都会。

    4.1:线性筛筛积性函数

    线性筛可以在线性时间内筛出大部分积性函数的前 nn 项的函数值。

    一般地,对于积性函数 f(x)f(x),若 f(pc)f(p^c) 的值便于分析。则该函数的前 nn 项的函数值可以被线性筛筛出来。

    我们要多维护一个数组 lowi\text{low}_i 表示:若 ii 的最小质因子为 p1p_1,其次数为 c1c_1,则 lowi=p1c1\text{low}_i = p_1^{c_1}。

    在线性筛的过程中,有特殊的两点:

    • 若当前遇到了一个质数 pp,则将 f(p),f(p2),f(p3),⋯ ,f(pc)f(p), f(p^2), f(p^3), \cdots, f(p^c) 都计算出来。
    • 在计算至少包含两个质因子的 ii 对应的函数值时,由积性函数定义得 f(i)=f(ilowi)⋅f(lowi)f(i) = f\left(\frac{i}{\text{low}_i}\right) \cdot f(\text{low}_i)。

    这样就可以在线性时间内筛出一个积性函数的前 nn 项了。对于一些简单的积性函数(例如 φ,μ\varphi, \mu)就有更简单的筛法,不一定需要维护 lowi\text{low}_i。

    4.1.1:线性筛筛欧拉函数

    • 设 pp 为质数,若 p∣np \mid n 且 p2∣np^2 \mid n,则 φ(n)=φ(np)⋅p\varphi(n) = \varphi(\frac{n}{p}) \cdot p。
    • 设 pp 为质数,若 p∣np \mid n 且 p2∤np^2 \nmid n,则 φ(n)=φ(np)⋅(p−1)\varphi(n) = \varphi(\frac{n}{p}) \cdot (p - 1)。
    const int SZ = 1e6;
    
    int pClock, prime[SZ + 10], fac[SZ + 10];
    int phi[SZ + 10];
    
    void sieve(int N) {
        phi[1] = 1;
        for (int i = 2; i <= N; i ++) {
            if (!fac[i]) fac[i] = i, prime[++ pClock] = i, phi[i] = i - 1;
            for (int j = 1; j <= pClock; j ++) {
                if (prime[j] > fac[i] || prime[j] > N / i) break;
                fac[i * prime[j]] = prime[j];
                phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
            }
        }
    }

    4.1.2:线性筛筛莫比乌斯函数

    • 设 pp 为质数,若 p∣np \mid n 且 p2∣np^2 \mid n,则 μ(n)=0\mu(n) = 0。
    • 设 pp 为质数,若 p∣np \mid n 且 p2∤np^2 \nmid n,则 μ(n)=−μ(np)\mu(n) = -\mu(\frac{n}{p})。
    const int SZ = 1e6;
    
    int pClock, prime[SZ + 10], fac[SZ + 10];
    int mu[SZ + 10]; 
    
    void sieve(int N) {
        mu[1] = 1;
        for (int i = 2; i <= N; i ++) {
            if (!fac[i]) fac[i] = i, prime[++ pClock] = i, mu[i] = -1;
            for (int j = 1; j <= pClock; j ++) {
                if (prime[j] > fac[i] || prime[j] > N / i) break;
                fac[i * prime[j]] = prime[j];
                mu[i * prime[j]] = mu[i] * (i % prime[j] ? -1 : 0);
            }
        }
    }

    4.1.3:线性筛筛各种积性函数

    根据积性函数的特殊性质。利用 lowi\text{low}_i 数组。可以在线性时间内筛出大部分积性函数的前 nn 项的函数值。

    请读者好好品味这段代码。

    const int SZ = 1e6;
    
    int pClock, prime[SZ + 10], low[SZ + 10];
    int f[SZ + 10];
    
    void sieve(int N) {
        f[1] = 1;
        for (int i = 2; i <= N; i ++) {
            if (!low[i]) {
                prime[++ pClock] = i;
    
                long long x = i;
                int c = 1;
                while (x <= N) {
                    low[x] = x;
                    // calculate f(x)
                    x *= i, c ++;
                }
            }
    
            for (int j = 1; j <= pClock; j ++) {
                if (prime[j] > N / i) break;
    
                if (i % prime[j] == 0)
                    low[i * prime[j]] = low[i] * prime[j];
                else
                    low[i * prime[j]] = prime[j];
    
                int num = i * prime[j]; 
                f[num] = f[num / low[num]] * f[low[num]];
    
                if (i % prime[j] == 0) break;
            }
        }
    }

    4.2:例题选讲

    4.2.1:【日常训练】挺好序列

    Description

    定义一个长度为 nn 的挺好序列 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n,满足:对于 ∀i∈[1,n]\forall i \in [1, n],都有 ai∣Aa_i | A。
    定义一个长度为 nn 的挺好序列 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n 的价值为 gcd⁡(a1,a2,⋯ ,an,B)\gcd(a_1, a_2, \cdots, a_n, B),其中 BB 为定值。

    给出三个正整数 n,m,Bn, m, B。定义 f(x)f(x) 为 A=xA = x 时所有挺好序列的价值和。请你求出:

    ∑i=1mf(i)\sum\limits_{i = 1}^m f(i)

    答案对 998244353998244353 取模。

    数据范围:1≤n≤10181 \leq n \leq 10^{18},1≤m≤2×1071 \leq m \leq 2 \times 10^7,1≤B≤10181 \leq B \leq 10^{18}。
    时空限制:3000 ms/512 MiB3000 \ \text{ms} /512 \ \text{MiB}。

    Solution

    结论

    f(x)f(x) 是积性函数。

    证明

    考虑任意互质的正整数对 x,yx, y。

    设序列 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n 是 A=xA = x 时的某个挺好序列,设序列 b1,b2,⋯ ,bnb_1, b_2, \cdots, b_n 是 A=yA = y 时的某个挺好序列。

    考虑生成序列 c1,c2,⋯ ,cnc_1, c_2, \cdots, c_n,其中 ci=aibic_i = a_ib_i,显然该序列是 A=xyA = xy 时的某个挺好序列。

    关注序列 cc 的价值。因为 x,yx, y 互质,所以 ai,bia_i, b_i 也一定互质。在唯一分解角度下观察,显然有:

    gcd⁡(a1,a2,⋯ ,an,B)⋅gcd⁡(b1,b2,⋯ ,bn,B)=gcd⁡(c1,c2,⋯ ,cn,B)\gcd(a_1, a_2, \cdots, a_n, B) \cdot \gcd(b_1, b_2, \cdots, b_n, B) = \gcd(c_1, c_2, \cdots, c_n, B)

    故序列 cc 的价值为序列 a,ba, b 的价值之积。

    回到积性函数的讨论上。f(x)⋅f(y)f(x) \cdot f(y) 的每一项,相当于是从 f(x)f(x) 与 f(y)f(y) 各选一项的乘积。故 f(x)⋅f(y)f(x) \cdot f(y) 是 A=xyA = xy 时所有挺好序列的价值和。

    所以 f(xy)=f(x)⋅f(y)f(xy) = f(x) \cdot f(y),所以 f(x)f(x) 为积性函数。

    Q.E.D


    注意到 1≤m≤2×1071 \leq m \leq 2 \times 10^7,可以考虑线性筛。按照上文「4.1.3:线性筛筛积性函数」的内容。现在要对于任意一个质数 pp,如何求出 f(pc)f(p^c)。

    对于一个质数 pp,令 dd 为满足 px∣Bp^x \mid B 的最大的 xx。可以简单分类讨论一下,不难得出:

    • 当 c≤dc \leq d 时:
    f(pc)=∑i=0cpi⋅[(c−i+1)n−(c−i)n]f(p^c) = \sum\limits_{i = 0}^c p^i \cdot \left[ (c -i + 1)^n - (c - i)^n \right]
    • 当 c>dc > d 时:
    f(pc)=pd⋅(c−d+1)n+∑i=0d−1pi⋅[(c−i+1)n−(c−i)n]f(p^c) = p^d \cdot (c - d + 1)^n + \sum\limits_{i = 0}^{d - 1} p^i \cdot \left[ (c -i + 1)^n - (c - i)^n \right]

    求出 f(p),f(p2),⋯ ,f(pc)f(p), f(p^2), \cdots, f(p^c) 后,灵活运用线性筛即可求出 f(x)f(x) 的前 mm 项,那么 ∑i=1mf(i)\sum\limits_{i = 1}^m f(i) 就直接算即可。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    typedef long long s64;
    
    int qpow(int a, s64 b, int p) {
        int ans = 1;
        for (; b; b >>= 1) {
            if (b & 1) ans = 1ll * ans * a % p;
            a = 1ll * a * a % p;
        }
        return ans;
    }
    
    const int SZ = 2e7;
    const int mod = 998244353;
    
    void add(int &x, const int &y) {
        x += y;
        if (x >= mod) x -= mod;
    }
    
    void dec(int &x, const int &y) {
        x -= y;
        if (x < 0) x += mod;
    }
    
    s64 n, B;
    int m;
    
    int pClock, prime[SZ + 10], low[SZ + 10];
    int f[SZ + 10];
    
    int get_top(int p) {
        int num = B, cnt = 0;
        while (num % p == 0) num /= p, cnt ++;
        return cnt;
    } 
    
    int power[100];
    
    void sieve(int N) {
        for (int i = 1; i < 100; i ++) power[i] = qpow(i, n, mod);
    
        f[1] = 1;
        for (int i = 2; i <= N; i ++) {
            if (!low[i]) {
                prime[++ pClock] = i;
    
                int d = get_top(i);
    
                s64 x = i;
                int c = 1;
    
                while (x <= N) {
                    low[x] = x;
    
                    if (c <= d) {
                        for (int j = 0, g = 1; j <= c; j ++, g = 1ll * g * i % mod) {
                            int rate = power[c - j + 1]; dec(rate, power[c - j]);
                            add(f[x], 1ll * g * rate % mod);
                        }
                    } else {
                        int g = 1;
                        for (int j = 0; j < d; j ++, g = 1ll * g * i % mod) {
                            int rate = power[c - j + 1]; dec(rate, power[c - j]);
                            add(f[x], 1ll * g * rate % mod);
                        }
                        add(f[x], 1ll * g * power[c - d + 1] % mod);
                    }
    
                    x *= i, c ++;
                }
            }
    
            for (int j = 1; j <= pClock; j ++) {
                if (prime[j] > N / i) break;
    
                if (i % prime[j] == 0)
                    low[i * prime[j]] = low[i] * prime[j];
                else
                    low[i * prime[j]] = prime[j];
    
                int num = i * prime[j];
                f[num] = 1ll * f[num / low[num]] * f[low[num]] % mod;
    
                if (i % prime[j] == 0) break;
            }
        } 
    }
    
    int main() {
        scanf("%lld%d%lld", &n, &m, &B);
    
        sieve(m);
    
        int ans = 0;
        for (int i = 1; i <= m; i ++) add(ans, f[i]);
    
        printf("%d\n", ans);
    
        return 0;
    }

    5:莫比乌斯反演

    已知两个数论函数 f,gf, g 满足:

    f(n)=∑d∣ng(d)f(n) = \sum\limits_{d \mid n}g(d)

    则:

    g(n)=∑d∣nf(d)∗μ(nd)g(n) = \sum\limits_{d \mid n} f(d) \ast \mu\left(\frac{n}{d}\right)

    证明

    已知条件等价于:

    f=g∗1f = g \ast 1

    两边同卷 μ\mu 可得:

    g∗ϵ=f∗μg=f∗μ\begin{aligned}g \ast \epsilon & = f \ast \mu \\g & = f \ast \mu\end{aligned}

    QED。

    5.1:例题选讲

    5.1.1:经典问题

    Description

    给出一个正整数 nn,求有多少个长度为 nn,循环节长度也恰好为 nn 的小写字符串。

    数据范围:1≤n≤1091 \leq n \leq 10^9。

    Solution

    设长度为 nn 的小写字符串有 f(n)f(n) 个;设长度为 nn,循环节长度也恰好为 nn 的小写字符串有 g(n)g(n) 个。

    显然有:

    f(n)=26nf(n) = 26^n

    以及:

    f(n)=∑d∣ng(n)f(n) = \sum\limits_{d \mid n} g(n)

    根据莫比乌斯反演,可得:

    g(n)=∑d∣n26d∗μ(nd)g(n) = \sum\limits_{d | n} 26^d \ast \mu\left(\frac{n}{d}\right)

    5.1.2:【Luogu P2522】「HAOI2011」Problem b

    Luogu P2522

    Description

    给出五个正整数 a,b,c,d,ka, b, c, d, k,请你求出:

    ∑a≤i≤b∑c≤j≤d[gcd⁡(i,j)=k]\sum\limits_{a \leq i \leq b} \sum\limits_{c \leq j \leq d} [\gcd(i, j) = k]

    共 TT 组询问。

    数据范围:1≤T,k≤5×1041 \leq T, k \leq 5 \times 10^4,1≤a≤b≤5×1041 \leq a \leq b \leq 5 \times 10^4,1≤c≤d≤5×1041 \leq c \leq d \leq 5 \times 10^4。
    时空限制:2500 ms/250 MiB2500 \ \mathrm{ms} / 250 \ \mathrm{MiB}。

    Solution

    记 calc(n,m)\text{calc}(n, m) 为:

    ∑i=1n∑j=1m[gcd⁡(i,j)=k]\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i, j) = k]

    简单容斥可得,答案为:

    calc(b,d)−calc(a−1,d)−calc(b,c−1)+calc(a−1,c−1)\text{calc}(b, d) - \text{calc}(a - 1, d) - \text{calc}(b, c - 1) + \text{calc}(a - 1, c - 1)

    考虑这样一个 calc(n,m)\text{calc}(n, m) 要怎么求,注意到 gcd⁡(i,j)=k\gcd(i, j) = k 与 gcd⁡(ik,jk)=1\gcd\left(\frac{i}{k}, \frac{j}{k}\right) = 1 是等价的,故原式化为:

    ∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd⁡(i,j)=1]∑i=1⌊nk⌋∑j=1⌊mk⌋ϵ(gcd⁡(i,j))\sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} [\gcd(i, j) = 1] \\\sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} \epsilon\left(\gcd(i, j)\right)

    利用 ϵ=μ∗1\epsilon = \mu \ast 1 反演,得:

    ∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd⁡(i,j)μ(d)\sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} \sum\limits_{d \mid \gcd(i, j)} \mu(d)

    交换枚举顺序,考虑先枚举 dd。要使得 d∣gcd⁡(i,j)d \mid \gcd(i, j),只需要让 d∣id \mid i 且 d∣jd \mid j 即可,故答案化为:

    ∑d=1min⁡(⌊nk⌋,⌊mk⌋)μ(d)⋅⌊nkd⌋⋅⌊mkd⌋\sum\limits_{d = 1}^{\min\left( \left\lfloor \frac{n}{k} \right\rfloor, \left\lfloor \frac{m}{k} \right\rfloor \right)} \mu(d) \cdot \left\lfloor \frac{n}{kd} \right\rfloor \cdot \left\lfloor \frac{m}{kd} \right\rfloor

    上式就比较好处理了。线性筛筛出莫比乌斯函数,求一遍莫比乌斯函数的前缀和,然后直接上数论分块。

    实现上,可以先令 n←⌊nk⌋,m←⌊mk⌋n \gets \left\lfloor \frac{n}{k} \right\rfloor, m \gets \left\lfloor \frac{m}{k} \right\rfloor,这样就比较好做了。

    时间复杂度 O(N+TN)\mathcal{O}(N + T\sqrt{N}),其中 NN 表示输入数据上界。

    5.1.3:【Luogu P1829】「国家集训队」Crash 的数字表格

    Luogu P1829

    Description

    给出两个正整数 n,mn, m,请你求出:

    ∑i=1n∑j=1mlcm(i,j)\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m \text{lcm}(i, j)

    答案对 2010100920101009 取模。

    数据范围:1≤n,m≤1071 \leq n, m \leq 10^7。
    时空限制:2000 ms/500 MiB2000 \ \mathrm{ms} / 500 \ \mathrm{MiB}。

    Solution

    不难发现原式为:

    ∑i=1n∑j=1mi×jgcd⁡(i,j)\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m \frac{i \times j}{\gcd(i, j)}

    令 d=gcd⁡(i,j)d = \gcd(i, j),考虑交换枚举顺序:

    ∑d=1min⁡(n,m)1d⋅∑d∣in∑d∣jm[gcd⁡(i,j)=d] i×j\sum\limits_{d = 1}^{\min(n, m)} \frac{1}{d} \cdot \sum\limits_{d \mid i}^n \sum\limits_{d \mid j}^m [\gcd(i, j) = d] \ i \times j

    将 ii 和 jj 中的 dd 提取出来,得:

    ∑d=1min⁡(n,m)d⋅∑i=1⌊nd⌋∑j=1⌊md⌋[gcd⁡(i,j)=1] i×j\sum\limits_{d = 1}^{\min(n, m)} d \cdot \sum\limits_{i = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{d} \right\rfloor} [\gcd(i, j) = 1] \ i \times j

    记:

    F(n,m)=∑i=1n∑j=1m[gcd⁡(i,j)=1] i×jF(n, m) = \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} [\gcd(i, j) = 1] \ i \times j

    考虑化简 F(n,m)F(n, m):

    F(n,m)=∑i=1n∑j=1mi×j×∑p∣gcd⁡(i,j)μ(p)=∑p=1min⁡(n,m)μ(p)⋅p2⋅∑i=1⌊np⌋∑j=1⌊mp⌋i×j\begin{aligned}F(n, m) & = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m i \times j \times \sum\limits_{p \mid \gcd(i, j)} \mu(p) \\& = \sum\limits_{p = 1}^{\min(n, m)} \mu(p) \cdot p^2 \cdot \sum\limits_{i = 1}^{\left\lfloor \frac{n}{p} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{p} \right\rfloor} i \times j\end{aligned}

    记:

    g(n,m)=∑i=1n∑j=1mi⋅j=∑i=1ni⋅∑j=1mj=n(n+1)2⋅m(m+1)2g(n, m) = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m i \cdot j = \sum\limits_{i = 1}^n i \cdot \sum\limits_{j = 1}^m j = \frac{n(n + 1)}{2} \cdot \frac{m(m + 1)}{2}

    则:

    F(n,m)=∑p=1min⁡(n,m)μ(p)⋅p2⋅g(⌊np⌋,⌊mp⌋)F(n, m) = \sum\limits_{p = 1}^{\min(n, m)} \mu(p) \cdot p^2 \cdot g\left(\left\lfloor \frac{n}{p} \right\rfloor, \left\lfloor \frac{m}{p} \right\rfloor\right)

    可以线性筛一下,然后数论分块。当 n,mn, m 同阶时,计算 F(n,m)F(n, m) 是 O(n)\mathcal{O}(\sqrt{n}) 的。

    回到本题,可得答案为:

    ∑d=1min⁡(n,m)d⋅F(⌊nd⌋,⌊md⌋)\sum\limits_{d = 1}^{\min(n, m)} d \cdot F\left(\left\lfloor \frac{n}{d} \right\rfloor, \left\lfloor \frac{m}{d} \right\rfloor\right)

    然后这个式子也可以数论分块做,本质上是一个数论分块套数论分块。

    线性筛的复杂度是 Θ(n)\Theta(n) 的。数论分块套数论分块的复杂度是 O(n34)\mathcal{O}(n^{\frac{3}{4}})。

    于是这题就这样做完了。

    关于「数论分块套数论分块」复杂度的证明

    原问题中最后计算答案的式子是一个二维数论分块套二维数论分块,看起来不太爽。我们把它替换成一个一维数论分块套一维数论分块,大概是这样:

    ∑d=1nd⋅F(⌊nd⌋)\sum\limits_{d = 1}^n d \cdot F\left(\left\lfloor \frac{n}{d} \right\rfloor\right)

    其中,计算 F(n)F(n) 的复杂度是 O(n)\mathcal{O}(\sqrt{n}) 的。考虑证明上式的复杂度。

    可以分类讨论一下:

    • 当 d≤nd \leq \sqrt{n} 时,最劣的情况是每一个 ⌊nd⌋\left\lfloor \frac{n}{d} \right\rfloor 互不相同,故此部分对复杂度的贡献为:
    ∑i=1nO(ni)\sum\limits_{i = 1}^{\sqrt{n}} \mathcal{O} \left( \sqrt\frac{n}{i} \right)
    • 当 d>nd > \sqrt{n} 时,注意到 ⌊nd⌋\left\lfloor \frac{n}{d} \right\rfloor 的值会均会落在区间 [1,n][1, \sqrt{n}] 中,最劣的情况是 ⌊nd⌋\left\lfloor \frac{n}{d} \right\rfloor 的值将 [1,n][1, \sqrt{n}] 里的所有数都取过一遍,故此部分对复杂度的贡献为:
    ∑i=1nO(i)\sum\limits_{i = 1}^{\sqrt{n}} \mathcal{O} \left( \sqrt{i} \right)

    简单积分近似一下:

    ∑i=1nO(i)+∑i=1nO(ni)≈O(∫0n12[x12+(nx)12]dx)\sum\limits_{i = 1}^{\sqrt{n}} \mathcal{O} \left( \sqrt{i} \right) + \sum\limits_{i = 1}^{\sqrt{n}} \mathcal{O} \left( \sqrt\frac{n}{i} \right) \thickapprox \mathcal{O} \left( \int_{0}^{n^\frac{1}{2}} \left[ x^\frac{1}{2} + \left( \frac{n}{x} \right)^\frac{1}{2} \right] \text{dx} \right)

    根据微积分基本定理,设 H(x)=23x32+n12⋅2x12H(x) = \frac{2}{3} x^{\frac{3}{2}} + n^{\frac{1}{2}} \cdot 2x^{\frac{1}{2}},有 H′(x)=x12+(nx)12H'(x) = x^{\frac{1}{2}} + \left( \frac{n}{x} \right)^{\frac{1}{2}}。则:

    ∫0n12[x12+(nx)12]dx=H(n12)−H(0)=83n34\int_{0}^{n^\frac{1}{2}} \left[ x^\frac{1}{2} + \left( \frac{n}{x} \right)^\frac{1}{2} \right] \text{dx} = H(n^{\frac{1}{2}}) - H(0) = \frac{8}{3} n^{\frac{3}{4}}

    故数论分块套数论分块的复杂度是 O(n34)\mathcal{O}(n^\frac{3}{4}) 的。

    5.1.4:【Luogu P2257】YY 的 GCD

    Luogu P2257

    Description

    给出两个正整数 n,mn, m,请你求出满足 1≤i≤n1 \leq i \leq n 且 1≤j≤m1 \leq j \leq m 的所有数对 (i,j)(i, j) 中,满足 gcd⁡(i,j)\gcd(i, j) 为质数的数对有多少个。

    共 QQ 组数据。

    数据范围:1≤Q≤1041 \leq Q \leq 10^4,1≤n,m≤1071 \leq n, m \leq 10^7。
    时空限制:4000 ms/500 MiB4000 \ \mathrm{ms} / 500 \ \mathrm{MiB}。

    Solution

    为了方便叙述,设质数集为 P\mathbb{P}。

    注意到答案为:

    ∑p∈P∑i=1n∑j=1m[gcd⁡(i,j)=p]∑p∈P∑i=1⌊np⌋∑j=1⌊mp⌋[gcd⁡(i,j)=1]∑p∈P∑i=1⌊np⌋∑j=1⌊mp⌋∑d∣gcd⁡(i,j)μ(d)∑p∈P∑d=1min⁡(⌊np⌋,⌊mp⌋)μ(d)⋅⌊npd⌋⋅⌊mpd⌋\sum\limits_{p \in \mathbb{P}} \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i, j) = p] \\\sum\limits_{p \in \mathbb{P}} \sum\limits_{i = 1}^{\left\lfloor \frac{n}{p} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{p} \right\rfloor} [\gcd(i, j) = 1] \\\sum\limits_{p \in \mathbb{P}} \sum\limits_{i = 1}^{\left\lfloor \frac{n}{p} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{m}{p} \right\rfloor} \sum\limits_{d \mid \gcd(i, j)} \mu(d) \\\sum\limits_{p \in \mathbb{P}} \sum\limits_{d = 1}^{\min(\left\lfloor \frac{n}{p} \right\rfloor, \left\lfloor \frac{m}{p} \right\rfloor)} \mu(d) \cdot \left\lfloor \frac{n}{pd} \right\rfloor \cdot \left\lfloor \frac{m}{pd} \right\rfloor

    考虑继续化简,令 T=pdT = pd,则上式化为:

    ∑p∈P∑d=1min⁡(⌊np⌋,⌊mp⌋)μ(d)⋅⌊nT⌋⋅⌊mT⌋∑T=1min⁡(n,m)⌊nT⌋⋅⌊mT⌋⋅∑p∣T,p∈Pμ(Tp)\sum\limits_{p \in \mathbb{P}} \sum\limits_{d = 1}^{\min(\left\lfloor \frac{n}{p} \right\rfloor, \left\lfloor \frac{m}{p} \right\rfloor)} \mu(d) \cdot \left\lfloor \frac{n}{T} \right\rfloor \cdot \left\lfloor \frac{m}{T} \right\rfloor \\\sum\limits_{T = 1}^{\min(n, m)} \left\lfloor \frac{n}{T} \right\rfloor \cdot \left\lfloor \frac{m}{T} \right\rfloor \cdot \sum\limits_{p | T, p \in \mathbb{P}} \mu\left(\frac{T}{p}\right)

    记 H(n)=∑p∣n,p∈Pμ(np)H(n) = \sum\limits_{p | n, p \in \mathbb{P}} \mu(\frac{n}{p}),则原式化为:

    ∑T=1min⁡(n,m)H(T)⋅⌊nT⌋⋅⌊mT⌋\sum\limits_{T = 1}^{\min(n, m)} H(T) \cdot \left\lfloor \frac{n}{T} \right\rfloor \cdot \left\lfloor \frac{m}{T} \right\rfloor

    考虑预处理出 H(n)H(n)。可以使用 “ 倍数法 “,对于每个质数 pp,让其去贡献它的每一个倍数 TT,稍微卡卡常也可以过。更高明的做法是挖掘 H(n)H(n) 的一些性质,然后使用线性筛将 H(n)H(n) 筛出来,这里直接给出结论:

    H(n)={1n∈P−H(np)+μ(np)p∣n,p2∤nμ(np)p∣n,p2∣nH(n) = \begin{cases}1 & n \in \mathbb{P} \\-H(\frac{n}{p}) + \mu(\frac{n}{p}) & p \mid n, p^2 \nmid n \\\mu(\frac{n}{p}) & p \mid n, p^2 \mid n\end{cases}

    预处理出 H(n)H(n) 后再处理出它的前缀和。这样就可以配合数论分块求出答案的值了。

    时间复杂度 O(n+Qn)\mathcal{O}(n + Q\sqrt{n})。

    5.1.5:【LOJ #6627】「XXOI 2019」等比数列三角形

    LOJ 6627

    Description

    给出一个正整数 nn。请你求出:有多少个合法的三角形,满足三边都是 ≤n\leq n 的整数,且三边成等比数列。

    数据范围:1≤n≤10121 \leq n \leq 10^{12}。
    时空限制:1000 ms/256 MiB1000 \ \mathrm{ms} / 256 \ \mathrm{MiB}。

    Solution

    枚举公差,将公差表示成一个既约分数 k=pq≥1k = \frac{p}{q} \geq 1 的形式,也就是说我们要保证 gcd⁡(p,q)=1\gcd(p, q) = 1。

    对于任意的一个三角形,不妨设三边中的最短边为 xx,则三边为 x,kx,k2xx, kx, k^2x。

    考虑公差 k=pqk = \frac{p}{q} 有一些什么限制:

    • 需要满足三角形的 “ 两边之和大于第三边 “,即:
    x+kx>k2x1≤k<1+52x + kx > k^2x \\1 \leq k < \frac{1 + \sqrt{5}}{2}

    设 e=1+52e = \frac{1 + \sqrt 5}{2},根据上面的两条限制,不难得出 qq 关于 pp 的取值范围:

    ⌈pe⌉≤q≤p\left\lceil \frac{p}{e} \right\rceil \leq q \leq p
    • 需要满足三角形的三边都是整数,即:
    p2q2x∈Zq2∣x\frac{p^2}{q^2}x \in \mathbb{Z} \\q^2 \mid x

    由于 q2∣xq^2 \mid x,可设 i=xq2i = \frac{x}{q^2},则答案为:

    ∑p∑⌈pe⌉≤q≤p[gcd⁡(p,q)=1]∑i=1[p2⋅i≤n]∑p=1n⌊np2⌋⋅∑⌈pe⌉≤q≤p[gcd⁡(p,q)=1]\sum\limits_{p} \sum\limits_{\left\lceil \frac{p}{e} \right\rceil \leq q \leq p} [\gcd(p, q) = 1] \sum\limits_{i = 1} [p^2 \cdot i\leq n] \\\sum\limits_{p = 1}^{\sqrt{n}} \left\lfloor \frac{n}{p^2} \right\rfloor \cdot \sum\limits_{\left\lceil \frac{p}{e} \right\rceil \leq q \leq p} [\gcd(p, q) = 1]

    记 S(n,p)=∑i=1n[gcd⁡(i,p)=1]S(n, p) = \sum\limits_{i = 1}^n [\gcd(i, p) = 1],考虑化简该函数:

    S(n,p)=∑i=1n∑d∣gcd⁡(i,p)μ(d)=∑d∣pμ(d)⋅⌊nd⌋\begin{aligned}S(n, p) & = \sum\limits_{i = 1}^n \sum\limits_{d \mid \gcd(i, p)} \mu(d) \\& = \sum\limits_{d \mid p} \mu(d) \cdot \left\lfloor \frac{n}{d} \right\rfloor\end{aligned}

    回到问题中,答案化为:

    ∑p=1n⌊np2⌋⋅[S(p,p)−S(⌈pe⌉−1,p)]\sum\limits_{p = 1}^{\sqrt{n}} \left\lfloor \frac{n}{p^2} \right\rfloor \cdot \left[ S(p, p) - S\left(\left\lceil \frac{p}{e} \right\rceil - 1, p\right) \right]

    使用 “ 倍数法 “,计算出函数 g(p)=S(p,p)−S(⌈pe⌉−1,p)g(p) = S(p, p) - S(\left\lceil \frac{p}{e} \right\rceil - 1, p),然后直接算即可。

    时间复杂度 O(nlog⁡n)\mathcal{O}(\sqrt{n} \log \sqrt{n})。

    6:杜教筛

    有时候,我们需要快速地对一些数论函数求前缀和,甚至是需要在低于线性时间的复杂度内求解。这时可以利用杜教筛来求出这些前缀和。

    一般地,给出一个数论函数 f(x)f(x),你需要求出 S(n)=∑i=1nf(i)S(n) = \sum\limits_{i = 1}^n f(i)。

    注意到,对于任意一个数论函数 gg,必定会满足:

    ∑i=1n(f∗g)(i)=∑i=1n∑d∣ig(d)⋅f(id)=∑i=1n∑j=1⌊ni⌋g(i)⋅f(j)=∑i=1ng(i)⋅∑j=1⌊ni⌋f(j)=∑i=1ng(i)⋅S(⌊ni⌋)\begin{aligned}\sum\limits_{i = 1}^n (f \ast g)(i) & = \sum\limits_{i = 1}^n \sum\limits_{d \mid i} g(d) \cdot f\left(\frac{i}{d}\right) \\& = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^{\left\lfloor \frac{n}{i} \right\rfloor} g(i) \cdot f(j) \\& = \sum\limits_{i = 1}^n g(i) \cdot \sum\limits_{j = 1}^{\left\lfloor \frac{n}{i} \right\rfloor} f(j) \\& = \sum\limits_{i = 1}^n g(i) \cdot S\left(\left\lfloor \frac{n}{i} \right\rfloor\right)\end{aligned}

    故有:

    g(1)S(n)=∑i=1n(f∗g)(i)−∑i=2ng(i)⋅S(⌊ni⌋)g(1)S(n) = \sum\limits_{i = 1}^n (f \ast g)(i) - \sum\limits_{i = 2}^n g(i) \cdot S\left(\left\lfloor \frac{n}{i} \right\rfloor\right)

    此时我们得到了一个 S(n)S(n) 关于 S(⌊ni⌋)S(\left\lfloor \frac{n}{i} \right\rfloor) 的递推式。若 f∗gf \ast g 与 gg 的前缀和都较好处理的话,就可以考虑使用数论分块来处理上面的递推式,较短时间内求出 S(n)S(n),因此找到一个合适的数论函数 gg 是关键。

    如果直接使用数论分块做上面的递推式,根据 ⌊nd⌋\left\lfloor \frac{n}{d} \right\rfloor 的取值进行分段。 不考虑递归的情况下,单纯去处理一个 S(n)S(n) 的复杂度是 O(n)\mathcal{O}(\sqrt{n}) 的,递归下去的复杂度为低阶小量 o(n)o(\sqrt{n}),故计算 S(n)S(n) 的复杂度为:

    O(n)+∑i=1nO(i)+∑i=1nO(ni)O(\sqrt{n}) + \sum\limits_{i = 1}^{\sqrt{n}} \mathcal{O}(\sqrt{i}) + \sum\limits_{i = 1}^{\sqrt{n}} \mathcal{O}\left(\sqrt{\frac{n}{i}}\right)

    简单积分近似一下:

    ∑i=1nO(i)+∑i=1nO(ni)≈O(∫0n12[x12+(nx)12]dx)=O(n34)\sum\limits_{i = 1}^{\sqrt{n}} \mathcal{O} \left( \sqrt{i} \right) + \sum\limits_{i = 1}^{\sqrt{n}} \mathcal{O} \left( \sqrt\frac{n}{i} \right) \thickapprox \mathcal{O} \left( \int_{0}^{n^\frac{1}{2}} \left[ x^\frac{1}{2} + \left( \frac{n}{x} \right)^\frac{1}{2} \right] \text{dx} \right) = \mathcal{O}(n^{\frac{3}{4}})

    可以积分近似证明,先线性筛预处理出 f(x)f(x) 的前 n23n^\frac{2}{3} 项,可以取得杜教筛的理论最优复杂度 O(n23)\mathcal{O}(n^\frac{2}{3})。

    对于一些较大的 nn,需要使用 std::map 来存下对应的值(记忆化),方便以后使用时直接计算出结果。

    6.1:例题选讲

    6.1.1:【Luogu P4213】Sum

    Luogu P4213

    Description

    给出一个正整数 nn,请你求出:

    ans1=∑i=1nφ(i)ans2=∑i=1nμ(i)ans_1 = \sum\limits_{i = 1}^n \varphi(i) \\ans_2 = \sum\limits_{i = 1}^n \mu(i)

    数据范围:1≤n<2311 \leq n < 2^{31}。
    时空限制:2000 ms/512 MiB2000 \ \mathrm{ms} / 512 \ \mathrm{MiB}。

    Solution

    莫比乌斯函数前缀和

    注意到 μ∗1=ϵ\mu \ast 1 = \epsilon,则考虑使用常数函数 1(n)=11(n) = 1 来构造递推式:

    S(n)=1−∑i=2nS(⌊ni⌋)S(n) = 1 - \sum\limits_{i = 2}^n S\left(\left\lfloor \frac{n}{i} \right\rfloor\right)

    然后直接筛即可。

    欧拉函数前缀和

    注意到 φ∗1=ID\varphi \ast 1 = \text{ID},则考虑使用常数函数 1(n)=11(n) = 1 来构造递推式:

    S(n)=n(n+1)2−∑i=2nS(⌊ni⌋)S(n) = \frac{n(n + 1)}{2} - \sum\limits_{i = 2}^n S\left(\left\lfloor \frac{n}{i} \right\rfloor\right)

    然后直接筛即可,但其实更好的做法是莫比乌斯反演。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <map>
    
    const int SZ = 1e6;
    
    int n;
    
    int m, prime[SZ + 10], fac[SZ + 10], mu[SZ + 10];
    
    int Smu[SZ + 10];
    
    void sieve(int N) {
        mu[1] = 1;
        for (int i = 2; i <= N; i ++) {
            if (!fac[i]) fac[i] = i, prime[++ m] = i, mu[i] = -1;
            for (int j = 1; j <= m; j ++) {
                if (prime[j] > fac[i] || prime[j] > N / i) break;
                fac[i * prime[j]] = prime[j];
                mu[i * prime[j]] = mu[i] * (i % prime[j] ? -1 : 0);
            }
        }
    
        for (int i = 1; i <= N; i ++)
            Smu[i] = Smu[i - 1] + mu[i];
    }
    
    std::map<int, int> Smu_buc;
    
    int Smu_calc(int n) {
        if (n <= SZ) return Smu[n];
        if (Smu_buc.count(n)) return Smu_buc[n];
    
        int cur = 1;
        for (long long x = 2, nx; x <= n; x = nx + 1) {
            nx = n / (n / x);
            cur -= (nx - x + 1) * Smu_calc(n / x);
        }
    
        return Smu_buc[n] = cur;
    }
    
    void work() {
        scanf("%d", &n);
    
        long long ans1 = 0;
        int ans2 = Smu_calc(n);
    
        for (long long x = 1, nx; x <= n; x = nx + 1) {
            nx = n / (n / x);
            ans1 += 1ll * (Smu_calc(nx) - Smu_calc(x - 1)) * (n / x) * (n / x);
        }
    
        ans1 = (ans1 + 1) / 2;
    
        printf("%lld %d\n", ans1, ans2);
    }
    
    int main() {
        sieve(SZ);
    
        int T;
        scanf("%d", &T);
    
        while (T --)    work();
    
        return 0;
    }

    6.1.2:【Luogu P3768】简单的数学题

    Luogu P3768

    Description

    给出一个正整数 nn,请你求出:

    ∑i=1n∑j=1ni⋅j⋅gcd⁡(i,j)\sum\limits_{i = 1}^n\sum\limits_{j = 1}^n i \cdot j \cdot \gcd(i, j)

    答案对给定的质数 pp 取模。

    数据范围:1≤n≤10101 \leq n \leq 10^{10},5×108≤p≤1.1×1095 \times 10^8 \leq p \leq 1.1 \times 10^9。
    时空限制:4000 ms/256 MiB4000 \ \mathrm{ms} / 256 \ \mathrm{MiB}。

    Solution

    利用 φ∗1=ID\varphi \ast 1 = \text{ID} 反演,得:

    ∑i=1n∑j=1ni⋅j⋅∑d∣gcd⁡(i,j)φ(d)∑d=1nφ(d)⋅∑d∣i∑d∣ji⋅j∑d=1nφ(d)⋅d2⋅∑i=1⌊nd⌋∑j=1⌊nd⌋i⋅j\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n i \cdot j \cdot \sum\limits_{d \mid \gcd(i, j)} \varphi(d) \\\sum\limits_{d = 1}^n \varphi(d) \cdot \sum\limits_{d \mid i} \sum\limits_{d \mid j} i \cdot j \\\sum\limits_{d = 1}^n \varphi(d) \cdot d^2 \cdot \sum\limits_{i = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum\limits_{j = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} i \cdot j

    记 F(n)=∑i=1ni=n(n+1)2F(n) = \sum\limits_{i = 1}^n i = \frac{n(n + 1)}{2},则答案化为:

    ∑d=1nφ(d)⋅d2⋅F2(⌊nd⌋)\sum\limits_{d = 1}^n \varphi(d) \cdot d^2 \cdot F^2\left(\left\lfloor \frac{n}{d} \right\rfloor\right)

    考虑使用数论分块处理上式,现在的问题是要求出函数 H(n)=φ(n)⋅n2H(n) = \varphi(n) \cdot n^2 的前缀和,考虑杜教筛。

    线性筛的部分相信大家都会,主要是讨论构造 S(n)=∑i=1nH(i)S(n) = \sum\limits_{i = 1}^n H(i) 关于 S(⌊ni⌋)S(\left\lfloor \frac{n}{i} \right\rfloor) 递推式的部分。

    注意到恒等函数 ID2\text{ID}_2,考虑将 HH 与 ID2\text{ID}_2 卷在一起:

    (H∗ID2)(n)=∑d∣nφ(d)⋅d2⋅(nd)2=∑d∣nφ(d)⋅n2=n2⋅∑d∣nφ(d)=n3\begin{aligned}(H \ast \text{ID}_2)(n) & = \sum\limits_{d \mid n} \varphi(d) \cdot d^2 \cdot \left(\frac{n}{d}\right)^2 \\& = \sum\limits_{d \mid n} \varphi(d) \cdot n^2 \\& = n^2 \cdot \sum\limits_{d | n} \varphi(d) \\& = n^3\end{aligned}

    于是可以得到 H∗ID2=ID3H \ast \text{ID}_2 = \text{ID}_3,我们发现 ID2\text{ID}_2 与 ID3\text{ID}_3 的前缀和都可以直接 Θ(1)\Theta(1) 计算(实在记不清楚公式的话,直接上拉格朗日插值吧),于是我们就可以得到 S(n)S(n) 的递推式:

    S(n)=(n(n+1)2)2−∑i=2ni2⋅S(⌊ni⌋)S(n) = \left( \frac{n(n + 1)}{2} \right)^2 - \sum\limits_{i = 2}^n i^2 \cdot S\left(\left\lfloor \frac{n}{i} \right\rfloor\right)

    直接上数论分块即可。

    6.1.3:【BZOJ #4804】欧拉心算(加强版)

    Description

    给出两个正整数 n,mn, m,请你求出:

    ∑i=1n∑j=1mφ(gcd⁡(i,j))\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m \varphi(\gcd(i, j))

    数据范围:1≤n,m≤1091 \leq n, m \leq 10^9。
    时空限制:1500 ms/512 MiB1500 \ \mathrm{ms} / 512 \ \mathrm{MiB}。

    Solution

    ∑i=1n∑j=1mφ(gcd⁡(i,j))=∑d=1φ(d)⋅∑i=1n∑j=1m[gcd⁡(i,j)=d]=∑d=1φ(d)⋅∑i=1⌊nd⌋∑j=1⌊md⌋[gcd⁡(i,j)=1]=∑d=1φ(d)⋅∑i=1⌊nd⌋∑j=1⌊md⌋∑p∣gcd⁡(i,j)μ(p)=∑d=1φ(d)⋅∑p=1μ(p)⋅⌊npd⌋⋅⌊mpd⌋\begin{aligned}\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m \varphi(\gcd(i, j))& = \sum\limits_{d = 1} \varphi(d) \cdot \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i, j) = d]\\& = \sum\limits_{d = 1} \varphi(d) \cdot \sum\limits_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \sum\limits_{j = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} [\gcd(i, j) = 1]\\& = \sum\limits_{d = 1} \varphi(d) \cdot \sum\limits_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \sum\limits_{j = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} \sum\limits_{p \mid \gcd(i, j)} \mu(p) \\& = \sum\limits_{d = 1} \varphi(d) \cdot \sum\limits_{p = 1} \mu(p) \cdot \left\lfloor\frac{n}{pd}\right\rfloor \cdot \left\lfloor\frac{m}{pd}\right\rfloor \end{aligned}

    记 T=pdT = pd,则式子化简为:

    ∑T=1min⁡(n,m)⌊nT⌋⋅⌊mT⌋⋅(∑d∣Tφ(d)⋅μ(Td))\sum\limits_{T = 1}^{\min(n, m)} \left\lfloor\frac{n}{T}\right\rfloor \cdot \left\lfloor\frac{m}{T}\right\rfloor \cdot \left(\sum\limits_{d \mid T} \varphi(d) \cdot \mu\left(\frac{T}{d}\right) \right)

    设 g=φ∗μg = \varphi \ast \mu(这里的 ∗\ast 是狄利克雷卷积,下文同),则式子化简为:

    ∑T=1min⁡(n,m)⌊nT⌋⋅⌊mT⌋⋅g(T)\sum\limits_{T = 1}^{\min(n, m)} \left\lfloor\frac{n}{T}\right\rfloor \cdot \left\lfloor\frac{m}{T}\right\rfloor \cdot g(T)

    可以用数论分块处理上式,现在的问题是要求 gg 的前缀和。可以考虑杜教筛,设:

    S(n)=∑i=1ng(i)S(n) = \sum\limits_{i = 1}^n g(i)

    记 d=1∗1d = 1 \ast 1,其中函数 1(n)=11(n) = 1,显然函数 dd 为约数个数函数。

    那么可以得到 S(n)S(n) 有关 S(⌊nd⌋)S\left(\left\lfloor\frac{n}{d}\right\rfloor\right) 的递推式:

    d(1)S(n)=∑i=1n(g∗d)(i)−∑i=2nd(i)⋅S(⌊ni⌋)d(1)S(n) = \sum\limits_{i = 1}^n (g \ast d)(i) - \sum\limits_{i = 2}^n d(i) \cdot S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)

    化简:

    d(1)S(n)=∑i=1n((φ∗1)∗(μ∗1))(i)−∑i=2nd(i)⋅S(⌊ni⌋)d(1)S(n)=n(n+1)2−∑i=2nd(i)⋅S(⌊ni⌋)d(1)S(n) = \sum\limits_{i = 1}^n \left((\varphi \ast 1) \ast (\mu \ast 1)\right)(i) - \sum\limits_{i = 2}^n d(i) \cdot S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \\d(1)S(n) = \frac{n(n + 1)}{2} - \sum\limits_{i = 2}^n d(i) \cdot S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)

    约数个数函数前缀和 ∑i=1hd(i)\sum\limits_{i = 1}^h d(i) 即为 ∑i=1h⌊hi⌋\sum\limits_{i = 1}^h \left\lfloor\frac{h}{i}\right\rfloor。直接用数论分块求解,复杂度较大。运用类似杜教筛的方法处理,具体地:

    • 对于 x≤n23x \leq n^{\frac{2}{3}} 的部分:运用线性筛求解每个 S(x),∑i=1xd(i)S(x), \sum_{i = 1}^x d(i)
    • 对于 x>n23x > n^{\frac{2}{3}} 的部分:运用数论分块求解 ∑i=1xd(i)\sum_{i = 1}^x d(i),运用递推式求解 S(x)S(x)。

    可以证明两部分的复杂度均为 O(n23)\mathcal{O}(n^{\frac{2}{3}}),直接上数论分块即可。