莫比乌斯反演

laihaochen · 2020-03-17 15:39:20 · 个人记录

设 a = bcp + q, 0 \leq q < bc，则 \lfloor{\frac{a}{bc}}\rfloor = p，\left\lfloor{\frac{\lfloor{\frac{a}{b}}\rfloor}{c}}\right\rfloor = \left\lfloor{\frac{cp + \lfloor{\frac{q}{b}}\rfloor}{c}}\right\rfloor = \left\lfloor{p + \frac{\lfloor{\frac{q}{b}}\rfloor}{c}}\right\rfloor = p +\left\lfloor{ \frac{\lfloor{\frac{q}{b}}\rfloor}{c}}\right\rfloor

又 0 \leq q \leq bc

\therefore \left\lfloor{\frac{q}{b}}\right\rfloor < c

\therefore \left\lfloor{ \frac{\lfloor{\frac{q}{b}}\rfloor}{c}}\right\rfloor < 1 \Rightarrow p +\left\lfloor{ \frac{\lfloor{\frac{q}{b}}\rfloor}{c}}\right\rfloor = p

\therefore \lfloor{\frac{a}{bc}}\rfloor = p = \left\lfloor{\frac{\lfloor{\frac{a}{b}}\rfloor}{c}}\right\rfloor

证明引理 2：

当 d \leq \sqrt{n} 时，\lfloor{\frac{n}{d}}\rfloor 至多有 \sqrt{n} 种取值。
当 d > \sqrt{n} 时，\lfloor{\frac{n}{d}}\rfloor < \sqrt{n}，也至多有 \sqrt{n} 种取值。

故 \forall n \in N, \left|\left\{\right\lfloor{\frac{n}{d}}\rfloor| d \in N\}\right| \leq \left\lfloor2\sqrt{n}\right\rfloor

2. 常见的数论函数

单位函数：\epsilon(n) = [n = 1]，[n = 1] 可以理解为一个 bool 值，当 n = 1 时，[n = 1] = 1，当 n \neq 1 时，[n = 1] = 0
常数函数：1(n) = 1
恒等函数：id(n) = n
除数函数：\sigma_k(n) = \sum_{d | n} d^k，特别地 \sigma_0(n) 通常被记为 d(n) 表示 n 的因数个数， \sigma_1(n) 通常被记为 \sigma(n) 表示因数和。

3. 整数分块

对于任意一个 i (i \leq n)，我们需要找到一个最大的 j(i \leq j \leq n)，使得 \left\lfloor\frac{i}{n}\right\rfloor = \left\lfloor\frac{j}{n}\right\rfloor，而 j = \left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor。

证明：

\because \left\lfloor\frac{i}{n}\right\rfloor \leq \frac{i}{n}

\therefore \left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor \geq \left\lfloor\frac{n}{\frac{n}{i}}\right\rfloor = \left\lfloor i\right\rfloor = i

\therefore i \leq \left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor

由引理 1，j = \left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor 时，\left\lfloor\frac{i}{n}\right\rfloor = \left\lfloor\frac{j}{n}\right\rfloor

所以我们在求类似 \sum_{i = 1}^n \left\lfloor\frac{i}{n}\right\rfloor 的式子时就可以把 \sum_{i = 1}^n 分成几块再求和。

例题：P2261 [CQOI2007]余数求和

题目大意：求 \sum_{i = 1}^n k \bmod i

\because k \bmod i = k - \left\lfloor\frac{k}{i}\right\rfloor

\therefore \sum_{i = 1}^n k \bmod i \Rightarrow \sum_{i = 1}^n k - \left\lfloor\frac{k}{i}\right\rfloor \Rightarrow n * k - \sum_{i = 1}^n \left\lfloor\frac{k}{i}\right\rfloor

所以，我们可以用整数分块求出 \sum_{i = 1}^n \left\lfloor\frac{k}{i}\right\rfloor

由引理 2 可以证明整数分块的时间复杂度为 O (\sqrt{n})

#include <cstdio>
#include <algorithm>
using namespace std;
long long n, k, gx;//记得开long long
int main() {
    scanf ("%lld%lld", &n, &k);
    long long ans = n * k;
    for (int x = 1; x <= n; x = gx + 1) {
        if (k / x == 0) {//如果为0了，那从x到n任意一数的k / x都为零
            gx = n;
        } else {
            gx = min (k / (k / x), n);
        }
        ans -= (k / x) * (x + gx) * (gx - x + 1) / 2;//等差数列求和公式
    }
    printf ("%lld\n", ans);
    return 0;
}

4. 积性函数

定义：

性质：

若 f, g 为积性函数，则当 h(x) = f(x^p), f^p(x), f(x)g(x), \sum_{d | x}f(d)g(\frac{x}{d}) 时，h(x) 也为积性函数。

证明第一个：

\forall \gcd (x, y) = 1, h(x) = f(x^p), h(y) = f(y^p), h(xy) = f((xy)^p)

又 f 为积性函数, \gcd (x^p, y^p) = 1

\therefore h(x)h(y) = f(x^p)f(y^p) = f(x^py^p) = f((xy)^p) = h(xy)

又 \gcd (x, y) = 1

--- 证明第二个： $\forall \gcd (x, y) = 1, h(x) = f^p(x), h(y) = f^p(y), h(xy) = f^p(xy)

又 f 为积性函数, \gcd (x, y) = 1

\overbrace{f(x)……f(x)}^{p}\overbrace{f(y)……f(y)}^{p} = \overbrace{f(x)f(y)……f(x)f(y)}^{p} = f^p(xy) = h(xy)

又 \gcd (x, y) = 1

--- 证明第三个： $\forall \gcd (x, y) = 1, h(x) = f(x)g(x), h(y) = f(y)g(y), h(xy) = f(xy)g(xy)

又 f, g 为积性函数, \gcd (x, y) = 1

\therefore h(x)h(y) = \Big(f(x)g(x)\Big)\Big(f(y)g(y)\Big) = \Big(f(x)f(y)\Big)\Big(g(x)g(y)\Big) = f(xy)g(xy) = h(xy)

又 \gcd (x, y) = 1

--- 证明第四个： $\forall \gcd (x, y) = 1, h(x) = \sum_{d_1 | x}f(d_1)g(\frac{x}{d_1}), h(y) = \sum_{d_2 | x}f(d_2)g(\frac{y}{d_2}), h(xy) = \sum_{d | x}f(d)g(\frac{xy}{d})

\because \gcd (x, y) = 1

\therefore \forall d_1 | x, d_2 | y, \gcd (d_1, d_2) = 1

又 f, g 为积性函数

\therefore h(x)h(y) = \sum_{d_1 | x}f(d_1)g(\frac{x}{d_1})\sum_{d_2 | x}f(d_2)g(\frac{y}{d_2}) = \sum_{d_1 | x}\sum_{d_2 | x}f(d_1)f(d_2)g(\frac{x}{d_1})g(\frac{y}{d_2}) = \sum_{d | xy}f(d)g(\frac{x}{d}) = h(xy)

又 \gcd (x, y) = 1

--- - $\epsilon, 1, id, \sigma_k$都是积性函数。 ## 5. 欧拉函数 **欧拉函数定义：**$\varphi(n) = \sum_{i = 1}^n [\gcd(i, n) = 1]

通式： n = \prod_{i = 1}^k p_i^{c_i} \rightarrow \varphi(n) = \prod_{i = 1}^k \frac{p_i - 1}{p_i}

证明：

\because \forall p | k, \sum_{x = 1}^k [p | x] = \frac{k}{p}

又 p_j (j \in [i + 1, k])| n * \frac{p_1 - 1}{p_1} * \frac{p_2 - 1}{p_2} * …… * \frac{p_i - 1}{p_i}

\therefore n = \prod_{i = 1}^k p_i^{c_i} \rightarrow \varphi(n) = \prod_{i = 1}^k \frac{p_i - 1}{p_i}

欧拉函数是积性函数：

证明：

$$ \left[ \begin{matrix} 1 & 2 & \cdots & r & \cdots & y\\ y + 1 & y + 2 & \cdots & y + r & \cdots & 2y\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\ (x - 1)y + 1 & (x - 1)y + 2 & \cdots & (x - 1)y + r & \cdots & xy\\ \end{matrix} \right] $$ 显然，这个矩阵中不重不漏地包含了 $[1, xy]$ 中的所有数。所以 $\varphi (xy) = \sum_{i = 1}^{xy} [\gcd(i, xy) = 1]

又 \gcd(x, y) = 1

\therefore \varphi (xy) = \sum_{i = 1}^{xy} [\gcd(i, x) = 1][\gcd(i, y) = 1]

\because \gcd(ky + r, y) = \gcd(r, y)

\therefore$ 每一列的元素均与 $y$ 互质的充要条件是 $\gcd(r, y) = 1

\therefore$ 共有 $\varphi(y)$ 列的所有元素满足 $\gcd(i, y) = 1

不难发现，每一列的所有元素构成模 x 的完全剩余系（简称完系）

故有且仅有 \varphi(x) 个元素满足 \gcd(i, x) = 1

故共有 \varphi(x)\varphi(y) 个元素满足 \gcd(i, x) = 1 且 \gcd(i, y) = 1

\therefore \varphi(xy) = \varphi(x)\varphi(y)

所以欧拉函数是积性函数。

因为欧拉函数是积性函数，所以可以利用线性筛来求。

在求之前，还要推出一个性质：

当 i \bmod p = 0，\varphi(i * p) = \varphi(i) * p

证明：

首先，证明两个引理：

当 x, i 不互质，则 x + i, i 不互质

设 g = \gcd(x, i) (g > 1)，则 x = gn, i = gm, \gcd(n, m) = 1

\therefore x + i = g(n + m)

\therefore \gcd (x + i, i) = g (g > 1)

当 x, i 互质，则 x + i, i 互质 (x < i)

反证：假设 g = \gcd(x + i, i) (g > 1)，则 x + i = gn, i = gm, \gcd(n, m) = 1 (n > m)

\therefore x = g(n - m)

有了这两个引理，我们可以得到 $[1, i]$ 中与 $i$ 互质的所有的数 $n$ 加上了 $i$ 恰好等于 $[i + 1, i + i]$ 中与 $i$ 互质的所有数。推广至 $p$，$[1, i * p]$ 中与 $i$ 互质的数的个数为 $\varphi(i) * p

又因为 i \bmod p = 0

\therefore p$ 的所有质因子都在 $i$ 的质因子中出现过，$[1, i * p]$ 中与 $i * p$ 互质的数的个数为 $\varphi(i) * p

故 \varphi(i * p) = \varphi(i) * p

phi[1] = 1;
for (int i = 2; i <= n; i++) {
    if (!vis[i]) {//i是质数，phi[i] = i - 1
        prime[++cnt] = i;
        phi[i] = i - 1;
    }
    for (int j = 1; j <= cnt && prime[j] * i <= n; j++) {
        vis[i * prime[j]] = 1; 
        if (i % prime[j] == 0) {
            phi[i * prime[j]] = phi[i] * prime[j];//性质
            break;
        }
        phi[i * prime[j]] = phi[i] * phi[prime[j]];//利用phi的积性
    }
}

6. 狄利克雷卷积

定义：

数论函数 f, g 的狄利克雷卷积为：(f * g)(n) = \sum_{d | n}f(d)g(\frac{n}{d})

性质：

狄利克雷卷积满足交换律和结合律

证明交换律：

(f * g)(n) = \sum_{d | n}f(d)g(\frac{n}{d})

令 d' = \frac{n}{d}

$\therefore \sum_{d | n}f(d)g(\frac{n}{d}) = \sum_{d' | n}f(\frac{n}{d'})g(d') = (g * f)(n)

证明结合律：

((f * g) * h)(n) = \sum_{(i * j) * k = n} f(i) * g(j) * h(k) = \sum_{i * (j * k)} f(i) * g(j) * h(k) = (f * (g * h))

两个积性函数的卷积也为积性函数

在积性函数的第四个已经证明。

\epsilon 为狄利克雷卷积的单位，即任何函数与 \epsilon 都为函数本身。

(f * \epsilon)(n) = \sum_{d | n} f(d) * \epsilon(\frac{n}{d}) = \sum_{d | n} f(d) * [\frac{n}{d} == 1] = \sum_{d | n} f(d) * [n == d] = f(n)

一些常用的卷积：

(1 * 1)(n) = \sum_{d | n} 1(d) * 1(\frac{n}{d}) = \sum_{d | n}1 = d(n)$，可简化表示为$1 * 1 = d

(id * 1)(n) = \sum_{d | n} id(d) * 1(\frac{n}{d}) = \sum_{d | n} d = \sigma(n)$，可简化表示为$id * 1 = \sigma

(\varphi * 1)(n) = \sum_{d | n} \varphi(d) * 1(\frac{n}{d}) = \sum_{d | n} \varphi(d) = id(n)$，可简化表示为$\varphi * 1 = id

下面证明第3个卷积：

设 n = \prod_{i = 1}^k p_i^{c_i}，由于 \varphi, 1均为积性函数

所以只需证明 (\varphi * 1)(p_i^{c_i}) = id(p_i^{c_i})即可。

设 n' = p_i^{c_i}

(\varphi * 1)(n') = \sum_{d | n'} \varphi(d) = \sum_{j = 0}^{c_i} \varphi(p_i^j)

又 \varphi(x) = x \prod_{j = 1}^k (1 - \frac{1}{p_j})

\therefore \varphi(p_i^j) = p_i^j * (1 - \frac{1}{p_i}) = p_i^j - p_i^{j - 1}

\therefore \sum_{j = 0}^{c_i} \varphi(p_i^j) = 1 + (p_i - 1) + (p_i^2 - p_i) + …… + (p_i^{c_i} - p_i^{c_i - 1}) = id(p_i^{c_i})

7. 莫比乌斯函数

定义：

\begin{array}{rcl} 1 & n = 1\\ 0 & \exists d, d^x | n(x > 1)\\ (-1)^{d(n)} & otherwise\\ \end{array} \right.

可以这样理解：

设 n = \prod_{i = 1}^k p_i^{c_i}，则：

\begin{array}{rcl} 1 & n = 1\\ 0 & \exists c_i > 1\\ (-1)^k & \forall c_i = 1\\ \end{array} \right.

\mu 函数的求法：

证明：

\forall \gcd(x, y) = 1

若 \mu(x) = 0 或 \mu(y) = 0

则说明 x 或 y 中含有大于1次方因子，则 xy 中含有大于1次方因子，则 \mu(x)(y) = 0 = \mu(x)\mu(y)

若 \mu(x), \mu(y) \neq 0

\because \gcd (x, y) = 1

\therefore$ $x, y$的所有质因子互不相同，且它们的质因子次数都是 $1

\therefore \mu(xy) = \mu(x)\mu(y)

综上，\mu 函数是积性函数。

因为 \mu 函数是积性函数，所以根据定义，我们可以在线性筛里求它：

mu[1] = 1;//定义
for (int i = 2; i <= n; i++) {
    if (!vis[i]) {//i是质数
        prime[++cnt] = i;//记录质数
        mu[i] = -1;//质数肯定为-1
    }
    for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {//线性筛模板
        vis[i * prime[j]] = 1;
        if (i % prime[j] == 0) {
            break;
        }
        mu[i * prime[j]] = -mu[i];//乘上一个质数就要改变一次符号，当mu[i]是0时还是为0
    }
}

性质：

\mu * 1 = \epsilon$，也即 $\sum_{d | n} \mu(d) = \epsilon(n)

证明：

当 n = 1 时，成立。
当 n \neq 1 时，令 n = \prod_{i = 1}^k p_i^{c_i}， \forall d | n 仅当 d 无平方因子时对答案才产生贡献。

结合二项式定理可得：

2. $\mu * id = \varphi

证明：

\because \varphi * 1 = id

\therefore \varphi * 1 * \mu = id * \mu

\therefore \varphi * (\mu * 1) = id * \mu

又 \mu * 1 = \epsilon

\therefore \varphi * \epsilon = id * \mu

\therefore id * \mu = \varphi

8. 四个技巧

1. \sum_{d | n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}

\because \mu * id = \varphi

\therefore \sum_{d | n} \mu(d) * id(\frac{n}{d}) = \varphi(n)

\therefore \sum_{d | n} \mu(d) * \frac{1}{d} = \frac{\varphi(n)}{n}

\therefore \sum_{d | n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}

2. \sum_{d | n}\mu(d) = \epsilon = [n = 1]

前面证过。

3. \sum_{i = 1}^n\sum_{j = 1}^mf(i) = \sum_{i = 1}^nf(i)\sum_{j = 1}^m

显然成立。

4. \sum_{k | n} = \sum_{k = 1}^n [k | n]

显然成立。

9. 反演公式

形式一：

若 F(n) = \sum_{d | n} f(d)，则 f(n) = \sum_{d | n}\mu(d)F(\frac{n}{d})

证明：

\because F(n) = \sum_{d | n} f(d)

\therefore f(n) = \sum_{d | n}\mu(d)F(\frac{n}{d})

\Leftrightarrow f(n) = \sum_{d | n}\mu(d)\sum_{k | \frac{n}{d}}f(k)

\Leftrightarrow f(n) = \sum_{d | n}\mu(d)\sum_{dk | n}f(k)

这一步其实就是更换了 d, k 的枚举顺序，看不懂可以带个例子。

\Leftrightarrow f(n) = \sum_{k | n}f(k)\sum_{dk | n}\mu(d)

\Leftrightarrow f(n) = \sum_{k | n}f(k)\sum_{d | \frac{n}{k}}\mu(d)

\Leftrightarrow f(n) = \sum_{k | n}f(k) [\frac{n}{k} = 1]

\Leftrightarrow f(n) = \sum_{k | n}f(k) [n = k]

\Leftrightarrow f(n) = f(n)

形式二：

若 F(n) = \sum_{n | d} f(d)，则 f(n) = \sum_{n | d} \mu(\frac{d}{n})F(d)

证明：

设 k = \frac{d}{n}，则 f(n) = \sum_{k = 1}^{+\infty} \mu(k)F(nk)

\because F(n) = \sum_{n | d} f(d)

\therefore f(n) = \sum_{k = 1}^{+\infty} \mu(k)F(nk)

\Leftrightarrow f(n) = \sum_{k = 1}^{+\infty}\mu(k)\sum_{nk | d}f(d)

这一步其实就是更换了 d, k 的枚举顺序，看不懂可以带个例子。

\Leftrightarrow f(n) = \sum_{d = 1}^{+\infty}f(d)\sum_{nk | d}\mu(k)

\Leftrightarrow f(n) = \sum_{d = 1}^{+\infty}f(d)\sum_{k | \frac{d}{n}}\mu(k)

\Leftrightarrow f(n) = \sum_{d = 1}^{+\infty}f(d)[\frac{d}{n} = 1]

\Leftrightarrow f(n) = \sum_{d = 1}^{+\infty}f(d)[d = n]

\Leftrightarrow f(n) = f(n)

一般来说，形式一会比形式二更常用，因为它跟狄利克雷卷积很像。

10. 应用

终于开始实践了 QAQ

P3455 [POI2007]ZAP-Queries

题目大意：求 \sum_{i = 1}^a\sum_{j = 1}^b[\gcd(i, j) = d]

（思路：看到了 [\gcd(i, j) = d] 我们就可以想办法让它变成 \epsilon，然后利用 \mu * 1 = \epsilon 进行转化）

我们不妨设 a \leq b

我们先把 i, j 除以 d

\Rightarrow \sum_{i = 1}^{\lfloor\frac{a}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{b}{d}\rfloor}[\gcd(i, j) = 1]

通过技巧 2

\Rightarrow \sum_{i = 1}^{\lfloor\frac{a}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{b}{d}\rfloor}\sum_{k | \gcd(i, j)} \mu(k)

通过技巧 4

\Rightarrow \sum_{i = 1}^{\lfloor\frac{a}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{b}{d}\rfloor}\sum_{k = 1}^a [k | \gcd(i, j)]\mu(k)

因为 i, j 的公因数必定是 \gcd (i, j) 的因数

\Rightarrow \sum_{i = 1}^{\lfloor\frac{a}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{b}{d}\rfloor}\sum_{k = 1}^a [k | i][k | j]\mu(k)

通过技巧 4 与技巧 3

\Rightarrow \sum_{k = 1}^a\mu(k)\sum_{k | i}^{\lfloor\frac{a}{d}\rfloor}\sum_{k | j}^{\lfloor\frac{b}{d}\rfloor}

\Rightarrow \sum_{k = 1}^a\mu(k)\lfloor\frac{a}{dk}\rfloor\lfloor\frac{b}{dk}\rfloor

\Rightarrow \sum_{k = 1}^a\mu(k)\lfloor\frac{\frac{a}{d}}{k}\rfloor\lfloor\frac{\frac{b}{d}}{k}\rfloor

所以我们有 O(na) 做法，但是 a \leq 5e4, n \leq 5e4，所以我们还要进一步优化。

(下面的 n 与题目的 n 不同)

我们发现 \lfloor\frac{\frac{a}{d}}{k}\rfloor\lfloor\frac{\frac{b}{d}}{k}\rfloor 可以使用整数分块优化成 O(\sqrt{n})

所以我们也要求出 \mu 函数的前缀和。

这样我们就得到了 O(n) 预处理， O(\sqrt{n}) 查询的做法。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e4 + 5;
int n, m, k, cnt, prime[N], mu[N], sum[N];
bool vis[N];
void init (int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + mu[i];
    }
}
void solve () {
    n /= k, m /= k;
    int gx, ans = 0;
    for (int x = 1; x <= min (n, m); x = gx + 1) {
        gx = min (n / (n / x), m / (m / x));
        ans += (sum[gx] - sum[x - 1]) * (n / x) * (m / x);
    }
    printf ("%d\n", ans);
}
int main() {
    init(5e4);
    int T;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%d%d", &n, &m, &k);
        solve ();
    }
    return 0;
}

P2522 [HAOI2011]Problem b

题目大意：\sum_{i = a}^b\sum_{j = c}^d [\gcd(i, j) = k]

\Rightarrow \sum_{i = 1}^b\sum_{j = 1}^d [\gcd(i, j) = k] - \sum_{i = 1}^b\sum_{j = 1}^c [\gcd(i, j) = k] - \sum_{i = 1}^a\sum_{j = 1}^d [\gcd(i, j) = k] + \sum_{i = 1}^a\sum_{j = 1}^c [\gcd(i, j) = k]

与 [POI2007]ZAP-Queries 类似，我们分别求出四个求和符号中的值就可以解决了。

这里就不放代码了。

P2257 YY的GCD

题目大意：求 \sum_{i = 1}^n \sum_{j = 1}^m [\gcd (i, j) = prime]

这次推的就较为简略了

\Rightarrow \sum_{k \in prime}\sum_{i = 1}^n \sum_{j = 1}^m [\gcd (i, j) = k]

根据 [POI2007]ZAP-Queries 的结果可以得到：

\Rightarrow \sum_{k \in prime}\sum_{d = 1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor

令 T = dk

\Rightarrow \sum_{k \in prime}\sum_{d = 1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor

\Rightarrow \sum_{d = 1}^{\lfloor\frac{n}{k}\rfloor}\sum_{k \in prime}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\mu(d)

\Rightarrow \sum_{T = 1}^n\sum_{k \in prime, k | T}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\mu(\frac{T}{k})

\Rightarrow \sum_{T = 1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k \in prime, k | T}\mu(\frac{T}{k})

我们发现 \sum_{k \in prime, k | T}\mu(\frac{T}{k}) 可以预处理。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e7 + 5;
int n, m, cnt, prime[N];
bool vis[N];
long long f[N], sum[N], mu[N];
void init (int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j * prime[i] <= n; j++) {
            f[j * prime[i]] += mu[j];
        }
    }
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + f[i];
    }
}
void solve () {
    long long ans = 0;
    for (int x = 1, gx; x <= min (n, m); x = gx + 1) {
        gx = min (n / (n / x), m / (m / x));
        ans += (long long)(sum[gx] - sum[x - 1]) * (n / x) * (m / x);
    }
    printf ("%lld\n", ans);
}
int main() {
    init(1e7);
    int T;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%d", &n, &m);
        solve ();
    }
    return 0;
}

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

题目大意：求 \sum_{i = 1}^n\sum_{j = 1}^m lcm(i, j) \pmod {20101009}

\Rightarrow \sum_{i = 1}^n\sum_{j = 1}^m \frac {i * j}{\gcd(i, j)}

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

\Rightarrow \sum_{d = 1}^nd\sum_{i = 1}^{\frac{n}{d}}\sum_{j = 1}^{\frac{m}{d}} i * j[\gcd(i, j) = 1]\pmod {20101009}

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

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

\Rightarrow \sum_{d = 1}^n\mu(d)\sum_{i = 1}^n\sum_{j = 1}^m i * j[d | \gcd(i, j)]

\Rightarrow \sum_{d = 1}^n\mu(d) * d^2\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor} i * j

令 g (n, m) = \sum_{i = 1}^n\sum_{j = 1}^m i * j

\Rightarrow \sum_{i = 1}^ni\sum_{j = 1}^mj

\Rightarrow \frac{n(n + 1)}{2}\frac{m(m + 1)}{2}

\begin{array}{rcl} \sum_{i = 1}^n\sum_{j = 1}^m lcm(i, j) = \sum_{d = 1}^nd * sum(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)\\ \\ sum(n, m) = \sum_{d = 1}^n\mu(d) * d^2 * g(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)\\ \\ g(n, m) = \frac{n(n + 1)}{2} * \frac{m(m + 1)}{2}\\ \end{array} \right.

我们可以利用整数分块来求解。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e7 + 5, mod = 20101009;
int n, m, ans, mu[N], sum[N];
bool notprime[N];
void init () {
    for (int i = 1; i <= n; i++) {
        mu[i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        if (notprime[i]) {
            continue;
        }
        mu[i] = -1;
        for (int j = 2 * i; j <= n; j += i) {
            notprime[j] = 1;
            if ((j / i) % i == 0) {
                mu[j] = 0;
            } else {
                mu[j] *= -1;
            }
        }
    }
    //根据不同的要求求不同的前缀和
    for (int i = 1; i <= n; i++) {
        sum[i] = (sum[i - 1] + (1ll * i * i % mod * (mu[i] + mod))) % mod;
    }
}
int g (int x, int y) {
    return (1ll * (x + 1) * x / 2 % mod) * (1ll * (y + 1) * y / 2 % mod) % mod;
}
int getsum (int a, int b) {
    int gx, res = 0;
    for (int x = 1; x <= a; x = gx + 1) {
        gx = min (a / (a / x), b / (b / x));
        res = (res + 1ll * (sum[gx] - sum[x - 1] + mod) * g(a / x, b / x) % mod) % mod;
    }
    return res;
}
int main() {
    scanf ("%d%d", &n, &m);
    if (n > m) {
        swap (n, m);
    }
    init();
    int gx;
    for (int x = 1; x <= n; x = gx + 1) {
        gx = min (n / (n / x), m / (m / x));
        ans = (ans + (1ll * (gx - x + 1) * (x + gx) / 2) % mod * getsum (n / x, m / x) % mod) % mod;
    }
    printf ("%d\n", ans);
    return 0;
}

P3327 [SDOI2015]约数个数和

题目大意：求 \sum_{i = 1}^n\sum_{j = 1}^md(ij)

首先证明一个引理：

d(ij) = \sum_{x | i}\sum_{y | j}[\gcd(x, y) = 1]

证明：

我们先考虑 i = p^a, j = p^b 的情况：

等式左边有 p^0, p^1, ……, p^{a + b} 共 (a + b + 1) 种因子，故 LHS = a + b + 1
等式右边可以分三种情况讨论：

x = p^m, 1 \leq m \leq a

\because \gcd(x, y) = 1

\therefore y = 0

共 a 种

y = p^n, 1 \leq n \leq b

\because \gcd(x, y) = 1

\therefore x = 0

共 b 种

x = 0, y = 0

$\therefore RHS = a + b + 1

\therefore LHS = RHS

所以当 i = p^a, j = p^b 是成立的。

因为 d 是积性函数，所以当 ij = \prod_{k = 1}^n p_k^{c_k} 时，d(i, j) = (\sum_{x | p_1^{a_1}}\sum_{y | p_1^{b_1}}[\gcd(x, y) = 1]\sum_{x | p_2^{a_2}}\sum_{y | p_2^{b_2}}[\gcd(x, y) = 1]……\sum_{x | p_n^{a_n}}\sum_{y | p_n^{b_n}}[\gcd(x, y) = 1])

\therefore d(ij) = \sum_{x | i}\sum_{y | j}[\gcd(x, y) = 1]

有了这个引理，我们可以将 \sum_{i = 1}^n\sum_{j = 1}^md(ij) 转换成：

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

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

\Rightarrow \sum_{d = 1}^n\mu(d)\sum_{i = 1}^n\sum_{j = 1}^m\sum_{x | i}\sum_{y | j}[d | i][d | j]

\Rightarrow \sum_{d = 1}^n\mu(d)\sum_{i = 1}^n\sum_{j = 1}^m\lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{j}\rfloor[d | i][d | j]

\Rightarrow \sum_{d = 1}^n\mu(d)\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{di}\rfloor\lfloor\frac{n}{dj}\rfloor

\Rightarrow \sum_{d = 1}^n\mu(d)\Big(\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{di}\rfloor\Big)\Big(\sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{dj}\rfloor\Big)

应用整数分块即可。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 50005;
int n, m, cnt, prime[N], mu[N], sum[N];
bool vis[N];
long long g[N];
void init (int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + mu[i];
    }
    for (int i = 1; i <= n; i++) {
        int gx;
        for (int x = 1; x <= i; x = gx + 1) {
            gx = i / (i / x);
            g[i] += (i / x) * (gx - x + 1);
        }
    }
}
int main() {
    init(50000);
    int T;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%d", &n, &m);
        int gx;
        long long ans = 0;
        for (int x = 1; x <= min (n, m); x = gx + 1) {
            gx = min (n / (n / x), m / (m / x));
            ans += 1ll * (sum[gx] - sum[x - 1]) * g[n / x] * g[m / x];
        }
        printf ("%lld\n", ans);
    }
    return 0;
}

P1447 [NOI2010]能量采集

题目大意：求 2 * \sum_{i = 1}^n\sum_{j = 1}^m \Big(\gcd(i, j) - 1\Big) + n * m

\Rightarrow 2 * \sum_{i = 1}^n\sum_{j = 1}^m \gcd(i, j) - n * m

令 g(n, m) = \sum_{i = 1}^n\sum_{j = 1}^m \gcd(i, j)

\because \varphi * 1 = id

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

\Rightarrow \sum_{d = 1}^n \varphi(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor

同样用线性筛 + 整数分块可求得。

#include <cstdio>
#include <algorithm> 
using namespace std;
const int N = 1e5 + 5;
long long n, m, cnt, ans, prime[N], phi[N], sum[N];
bool vis[N];
void init (int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && prime[j] * i <= n; j++) {
            vis[i * prime[j]] = 1; 
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + phi[i];
    }
}
int main() {
    init(1e5);
    scanf ("%lld%lld", &n, &m);
    if (n > m) {
        swap(n, m);
    }
    for (int x = 1, gx; x <= n; x = gx + 1) {
        gx = min (n / (n / x), m / (m / x));
        ans += (long long)(sum[gx] - sum[x - 1]) * (n / x) * (m / x); 
    }
    printf ("%lld\n", ans * 2ll - n * m);
    return 0;
}

P3172 [CQOI2015]选数

题目大意：求出 \sum_{a'_1 = l}^r\sum_{a'_2 = l}^r\cdots\sum_{a'_n = l}^r [\gcd(\sum_{i = 1}^n a'_i) = k]

\because l \leq a'_i = a_i * k \leq r, i \in [1, n]

\therefore \left\lceil\frac{l}{k}\right\rceil \leq a_i \leq \left\lfloor\frac{r}{k}\right\rfloor, i \in [1, n]

令 L = \left\lceil\frac{l}{k}\right\rceil = \left\lfloor\frac{l - 1}{k}\right\rfloor + 1, R = \left\lfloor\frac{r}{k}\right\rfloor

\Rightarrow \sum_{a_1 = L}^{R}\sum_{a_2 = L}^{R}\cdots\sum_{a_n = L}^{R} [\gcd(\sum_{i = 1}^n a_i) = 1]

\Rightarrow \sum_{d | \gcd(\sum_{i = 1}^n a_i)} \mu(d) \sum_{a_1 = L}^{R}\sum_{a_2 = L}^{R}\cdots\sum_{a_n = L}^{R}

\Rightarrow \sum_{d = 1}^R \mu(d)\sum_{a_1 = L}^R[d | a_1]\sum_{a_2 = L}^R[d | a_2]\cdots\sum_{a_n = L}^R[d | a_n]

\Rightarrow \sum_{d = 1}^R \mu(d)\sum_{a_1 = \left\lceil\frac{L}{d}\right\rceil}^{\left\lfloor\frac{R}{d}\right\rfloor}\sum_{a_2 = \left\lceil\frac{L}{d}\right\rceil}^{\left\lfloor\frac{R}{d}\right\rfloor}\cdots\sum_{a_n = \left\lceil\frac{L}{d}\right\rceil}^{\left\lfloor\frac{R}{d}\right\rfloor}

\Rightarrow \sum_{d = 1}^R \mu(d)\Big(\left\lfloor\frac{R}{d}\right\rfloor - \left\lceil\frac{L}{d}\right\rceil + 1\Big)^n

又 \left\lceil\frac{L}{d}\right\rceil = \left\lfloor\frac{L - 1}{d}\right\rfloor + 1

\Rightarrow \sum_{d = 1}^R \mu(d)\Big(\left\lfloor\frac{R}{d}\right\rfloor - \left\lfloor\frac{L - 1}{d}\right\rfloor\Big)^n

另外，这道题用线性筛会炸，要用杜教筛优化

#include <cstdio>
#include <tr1/unordered_map>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, k, l, r, ans, cnt, prime[N], mu[N];
bool vis[N];
tr1::unordered_map <int, int> ans_mu;
void init (int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        } 
    }
    for (int i = 1; i <= n; i++) {
        mu[i] += mu[i - 1];
    }
}
int get_mu (int n) {
    if (n <= 1e6) {
        return mu[n];
    }
    if (ans_mu[n]) {
        return ans_mu[n];
    }
    int ans = 1;
    for (int x = 2, gx; x <= n; x = gx + 1) {
        gx = n / (n / x);
        ans -= (gx - x + 1) * get_mu (n / x);
    }
    return ans_mu[n] = ans;
}
int f (int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (1ll * res * a) % mod;
        }
        b >>= 1;
        a = (1ll * a * a) % mod;
    }
    return res % mod;
}
void solve () {
    for (int x = 1, gx; x <= r; x = gx + 1) {
        if (l < x) {//这里因为x最多能到r，所以要特判一下，不能直接写min (l, r)因为gcd(a1, a2, ... , an)可能会大于l 
            gx = r / (r / x);
        } else {
            gx = min (l / (l / x), r / (r / x));
        }
        ans = (ans + (1ll * (get_mu (gx) - get_mu(x - 1)) * f (r / x - l / x, n)) % mod) % mod;
    }
    printf ("%d\n", (ans + mod) % mod);
}
int main() {
    scanf ("%d%d%d%d", &n, &k, &l, &r);
    l = (l - 1) / k, r /= k;
    init (1e6);
    solve ();
    return 0;
}

莫比乌斯反演

目录

1. 两个引理

2. 常见的数论函数

3. 整数分块

4. 积性函数

5. 欧拉函数

6. 狄利克雷卷积

7. 莫比乌斯函数

8. 四个技巧

9. 反演公式

10. 应用

1. 两个引理

2. 常见的数论函数

3. 整数分块

4. 积性函数

6. 狄利克雷卷积

定义：

性质：

7. 莫比乌斯函数

8. 四个技巧

1. \sum_{d | n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}

2. \sum_{d | n}\mu(d) = \epsilon = [n = 1]

3. \sum_{i = 1}^n\sum_{j = 1}^mf(i) = \sum_{i = 1}^nf(i)\sum_{j = 1}^m

4. \sum_{k | n} = \sum_{k = 1}^n [k | n]

9. 反演公式

10. 应用

P3455 [POI2007]ZAP-Queries

P2522 [HAOI2011]Problem b

P2257 YY的GCD

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

P3327 [SDOI2015]约数个数和

P1447 [NOI2010]能量采集

P3172 [CQOI2015]选数