从1开始的数论

Posted on Edited on In Word count in article: 3k Reading time ≈ 11 mins.
洛谷网课

基础知识

  • 整除
  • 互质
  • 素数
  • 取整函数
  • 最大公约数(最小公倍数)

整数分块

易证已知\(d,n\in\mathbb{Z}\;且\;d\le n\) , 那么\([\frac nd]\)的取值不会超过\(\sqrt n\)个

调和数

调和数的定义为

\[ H_n=\sum\limits_{k=1}^n\frac1k \] 关于调和数有如下结论: \[ H_n=\ln n+\lambda+O(1) \] 可以推出一个常见的事见复杂度: \[ \sum\limits_{d=1}^n\left[\frac nd\right]=\Theta(n\log n) \] ## 素数计数函数

令素数计数函数\(\pi(n)\)表示不超过\(n\)的素数个数. 我们有如下的素数定理 : \[ \pi(n)\sim\frac n{\ln n} \]

推论:

  • \(n\)附近的素数密度近似为\(\frac 1{\ln n}\)
  • 第\(n\)个素数\(p_n\sim n\ln n\)

素数计数

显然可以利用 \(Euler\) 筛算出 \(n\) 以内的所有素数，进而得到 \(\pi(n)\)。 存在更快的做法。可惜一页课件太少，写不下。

用一种类似积性函数求和的筛法可以达到 \(O(\frac{n^{\frac34}}{\log n})\) 的复杂度。 先进的做法似乎可以达到 \(O(\frac{n^\frac 23}{\log n})\) 。

算数基本定理

任意一个正整数 \(n\) 都可以表示成素数的乘积的形式：

\[ n = p_1^{a_1}p_2^{a_2}\cdots p_s^{a_3} \] 式中 \(p_1,\cdots, p_s\) 是不同素数。且不计次序的情况下，这一表达是唯一的。

数论函数

积性函数

设 \(f\) 是数论函数，若对任意互质的正整数 \(a,\;b\)，都有 \(f(ab) = f(a)f(b)\)，则称 \(f\) 是积性函数。

若对任意的正整数 \(a, b\)，都有 \(f(ab) = f(a)f(b)\)，则称 \(f\) 是完全积性的。

若 \(f\) 是积性函数，且 \(n = p_1^{\alpha_1}p_2^{\alpha_2}\dots p_s^{\alpha_s}\) 是 \(n\) 的标准分解，则 有 \(f(n) = f(p_1^{\alpha_1} )f(p_2^ {\alpha_2} )\cdots(p_s^{\alpha_s} )\) 因此研究积性函数 \(f\) 可以转化为研究 \(f(p^α)\)，即 f 在素数和素数的幂上的取值。

设 \(f\) 是积性函数，为求 \(f(n)\)，可以对 \(n\) 分解素因子，然后计算所有的 \(f(p^α)\) 乘起来。 如果要对 \(1\) 到 \(n\) 之间的所有数求出 \(f\)，注意到 \(Euler\) 筛法的过程中可以求出每个数的最小素因子和最小素因子的幂次，利用此就能在线性时间内计算出所需的 \(f\) 的值。

除数函数

除数函数\(\delta_k(n)\)用来表示\(n\)的因子的\(k\)次方之和: \[ \sigma_k(n)=\sum\limits_{d|n}{}d^k \] 约数个数\(\delta_0(n)\)常记为\(d(n)\), 约束和\(\delta_1(n)\)常记为\(\delta(n)\)

\(Dirichlet\)卷积

设 \(f, g\) 是数论函数，考虑数论函数 \(h\) 满足: \[ h(n)=\sum\limits_{d|n}f(d)g(\frac nd) \] 则称\(h\)为\(f\)与\(g\)的\(Dirichlet\)卷积, 记作\(h=f*g\)

单位函数 \(\epsilon\) 是 \(Dirichlet\) 卷积的单位元，即对于任意函数 \(f\)，有 \(\epsilon ∗ f = f ∗ \epsilon = f\)。

\(Dirichlet\) 卷积满足交换律和结合律

如果 \(f,g\) 都是积性函数，那么 \(h = f ∗ g\) 也是积性函数。

除数函数的定义可以写为： \(\delta_k = 1 ∗ Id_k\)

\(Euler\) 函数的性质可以写为： \(Id = \varphi ∗ 1\)

设 \(f, g\) 是数论函数，计算 \(f\) 和 \(g\) 的 \(Dirichlet\) 卷积在 \(n\) 处的值 需要枚举 \(n\) 的所有约数

如果要计算 \(f\) 和 \(g\) 的 \(Dirichlet\) 卷积的前 \(n\) 项，可以枚举 \(1\) 到 \(n\) 中每个数的倍数，根据调和数的相关结论，这样做的复杂度是 \(O(n\log n)\)

无平方因子数

求 \(n\) 以内的无平方因子数的个数。亦即，求 \[ \sum\limits_{k=1}^n\mu^2(k) \] 我们考虑一个素数 \(p\)，那么 \(p^2\) 的倍数都有平方因子，个数是 \(\left\lfloor \frac n {p^2} \right\rfloor\) ，应该从答案中去掉

但是这样多去掉了一些数。比如对于不同的素数 \(p_1, p_2，p_1^2p_2^2\) 的倍数就被去掉了两次，个数是 \(\left\lfloor\frac n {p_1^2p_2^2}\right\rfloor\) ，应该加回来

显然这是容斥原理

如果 \(d\) 是 \(s\) 个不同素数的乘积，那么其对答案的贡献是 \((−1)^s \left\lfloor \frac n {d^2} \right\rfloor\) 。 如果 \(d\) 不是不同素数的乘积，即 \(d\) 有平方因子，那么 \(d\) 对答案没有贡献。 容斥的系数恰好是 \(Mobius\) 函数

因此, 答案为: \[ \sum\limits_{k=1}^n=\sum\limits_{d=1}^{\sqrt n}\mu(d)\left\lfloor \frac n{d^2}\right\rfloor \] 事实上，\(Mobius\) 反演本身就可以看成是对整除关系的容斥

杜教筛

有一种利用 \(Dirichlet\) 卷积来构造递推式，从而对一些数论函数 进行快速求和的方法

民间称呼杜教筛

我们用两个例子来了解一下这个方法

例一:

令: \[ \phi(n)=\sum\limits_{k=1}^n\varphi(k) \] 找出高效求出\(\phi(n)\)值的方法

考虑\(ID=\varphi*1\), 可以的到: \[ \begin{align*} \frac 12n(n+1)&=\sum_{k=1}^nk=\sum_{k=1}^n\sum_{d|k}\varphi(\frac kd)\\ &=\sum_{d=1}^n\;\sum_{1\le k\le n\\~~ d|k}\varphi(\frac kd)\\ &=\sum_{d=1}^n\sum_{k=1}^{\left\lfloor\frac nd\right\rfloor}\varphi(k)\\ &=\sum_{d=1}^n\phi(\left\lfloor\frac nd\right\rfloor) \end{align*} \]

即, 我们得到了: \[ \frac12n(n+1)=\sum_{d=1}^n\phi(\left\lfloor\frac nd\right\rfloor)=\phi(n)-\sum_{d=2}^n\phi(\left\lfloor\frac nd\right\rfloor)\\ \therefore \phi(n)=\frac12n(n+1)-\sum_{d=2}^n\phi(\left\lfloor\frac nd\right\rfloor) \] 因此，如果对于 \(2 \le d \le n\) 已经计算出了 \(\phi(\left\lfloor\frac nd\right\rfloor)\)，即特殊点处 的函数值，由于特殊点只有不超过 \(2\sqrt n\) 个，利用之前见过的分段的方法，我们可以在 \(O(\sqrt n)\) 的时间内计算 \(\phi(n)\)

而计算 \(\phi(\left\lfloor \frac nd \right\rfloor)\) 是子问题，可以递归解决

递归过程中会不会需要计算更多的函数值？

由特殊点的性质，可以发现所有要计算的就是所有的特殊点处的 函数值

使用记忆化搜索，这样每个函数值只会被计算一遍

例二:

令 \[ M(n)=\sum_{k=1}^n\mu(k) \] 计算原理类似 \[ \begin{align*} 1&=\sum_{k=1}^n\epsilon(k)=\sum_{k=1}^n\sum_{d|k}\mu(\frac kd)\\ &=\sum_{d=1}^n\sum_{1\le k\le n\\~~d|k}\mu(\frac kd)\\ &=\sum_{d=1}^n\sum_{k=1}^\frac nd\mu(k)\\ &=\sum_{d=1}^nM(\left\lfloor\frac nd\right\rfloor) \end{align*} \] 即, 我们得到了: \[ M(n)=1-\sum_{d=2}^nM(\left\lfloor\frac nd\right\rfloor) \] 同理可以求得

Code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
unordered_map <int, int> Mu;
unordered_map <int, ll> Phi;
const int Maxn = 5e6;
int T, A, B;
int P[Maxn + 10], Cnt;
int mu[Maxn + 10];
ll phi[Maxn + 10];
bool Vis[Maxn + 10];

inline void Init()
{
    mu[1] = phi[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) P[++Cnt] = i, mu[i] = -1, phi[i] = i - 1;
        for (int j = 1; j <= Cnt && i * P[j] <= Maxn; ++j)
        {
            Vis[i * P[j]] = 1;
            if (i % P[j]) mu[i * P[j]] = -mu[i], phi[i * P[j]] = phi[i] * phi[P[j]];
            else 
            {
                phi[i * P[j]] = phi[i] * P[j];
                break;
            }
        } 
    }
    for (int i = 1; i <= Maxn; ++i) mu[i] += mu[i - 1], phi[i] += phi[i - 1];
}

inline ll PPhi(int x)
{
    if (x <= Maxn) return phi[x];
    if (Phi[x]) return Phi[x];
    ll Ans = 1ll * x * (x + 1) / 2;
    for (ll l(2), r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        Ans -= (r - l + 1) * PPhi(x / l);
    }
    return Phi[x] = Ans;
}

inline int MMu(int x)
{
    if (x <= Maxn) return mu[x];
    if (Mu[x]) return Mu[x];
    ll Ans(1);
    for (ll l(2), r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        Ans -= (r - l + 1) * MMu(x / l);
    }
    return Mu[x] = Ans;
}

int main()
{
    Init();
    scanf ("%d", &T);
    while (T--)
    {
        scanf ("%d", &A);
        printf ("%lld %d\n", PPhi(A), MMu(A));
    }
}

时间复杂度分析

算法的总时间复杂度就是计算所有特殊点处的函数值的时间复杂度

回忆特殊点的结构，时间复杂度 \(T(n)\) 可以估计为 \[ T(N)=\sum_{i=1}^{\sqrt n}O(\sqrt i)+\sum_{i=1}^{\sqrt n}O(\sqrt{\left\lfloor\frac ni\right\rfloor}) \] 显然式中第一项渐进意义上小于第二项, \(DaWuMiMan\)

而对于式中第二项我们可以利用积分估计: \[ \sum_{i=1}^{\sqrt n}O(\sqrt{\left\lfloor\frac ni\right\rfloor})=O(\int_1^{\sqrt n}\sqrt\frac nx{\rm d}x)=O(n^{\frac12}\cdot n^{\frac14})=O(n^{\frac34}) \] 于是算法的时间复杂度为 \(O(n^{\frac34})\) 。

注意到我们还可以使用 \(Euler\) 筛求出 \(\varphi\) 的值，进而求出前缀和

假设我们使用 \(Euler\) 筛预先求出了 \(\varphi\) 的前 \(S\) 项，那么递归部分的时间复杂度变为： \[ \sum_{i=1}^{\frac ns}O(\sqrt{\left\lfloor\frac ni\right\rfloor})=O(\int_1^\frac nS\sqrt\frac nx{\rm d}x)=O(n^\frac12\cdot\sqrt\frac nS)=O(\frac n{S^\frac12}) \] 结合 \(Euler\) 筛的时间复杂度 \(O(S)\)，总的时间复杂度为\(O(S+\frac n{S^\frac12})\)

如果取 \(S = n^\frac23\)，那么总的时间复杂度为 \(O(n^\frac23)\)

一般化

在求 \(\varphi\) 和 \(\mu\) 的前缀和的过程中，我们都利用了一个 \(Dirichlet\) 卷积。

这就让我们考虑数论函数 \(f, g\) 的前缀和与他们的 \(Dirichlet\) 卷积 \(f ∗ g\) 的前缀和之间的关系。

用 \(F\) 表示 \(f\) 的前缀和, \(h=f*g\)，我们有 \[ \begin{align*} \sum_{k=1}^nh(k)&=\sum_{k=1}^n\sum_{d|k}f(\frac kd)g(d)\\ &=\sum_{d=1}^n\sum_{1\le k\le n\\~~d|k}g(d)f(\frac kd)\\ &=\sum_{d=1}g(d)\sum_{k=1}^{\left\lfloor\frac nd\right\rfloor}f(k)\\ &=\sum_{d=1}^ng(d)F(\left\lfloor\frac nd\right\rfloor) \end{align*} \] 在上两例中，\(f ∗ g\) 和 \(g\) 的前缀和都可以 \(O(1)\) 得出，因此 \(f\) 可 以用杜教筛计算

其实并不需要如此强的性质

可以看到，在杜教筛的过程中，我们实际上求出了所有特殊点处的前缀和。

注意到 \(g\) 的前缀和是对使得 \(\left\lfloor\frac nd\right\rfloor\) 相同 \(d\) 分段的时候用到的，因此只需要用到 \(g\) 在段落端点处的前缀和。

可以发现，段落的端点恰好是所有的特殊点。

因此，\(f, g\) 以及 \(f ∗ g\) 这三个函数中，只要有两个可以用不弱于杜教筛的方法求值，就可以杜教筛第三个。

杂项

\(Euler\)定理

\(Euler\) 定理指出，对于正整数 \(n\) 以及与 \(n\) 互质的正整数 \(a\)，有 \[ a^{\varphi(n)}\equiv1\pmod n \]

一个常用结论

对于正整数 \(n\) 与正整数 \(a\)，\(Euler\) 定理说明如果 \(a\perp n\)，那么对 于任意的 \(m\)，有 \[ a^m\equiv a^{m\mod \varphi(n)}\pmod n \] 如果 \(a\) 与 \(n\) 不一定互质，若 \(m \ge \varphi(n)\)，我们也有以下结论 \[ a^m\equiv a^{m \mod \varphi(n)\;+\;\varphi(n)}\pmod n \]

阶

给定正整数 \(n\)，对于 \(a\) 满足 \(a\perp n\)，定义 \(a\) 模 \(n\) 的阶为最小的正整数 \(d\) 使得下式成立： \[ a^d\equiv1\pmod n \] \(a\)模\(n\)的阶记作\(\delta_n(a)\)

由 \(Euler\) 定理可以得到 \(\delta_n(a) | \varphi(n)\)

原根

若 \(\delta_n(a) = \varphi(n)\)，则称 \(a\) 是模 \(n\) 的原根。 可以看出，\(a\) 是模 \(n\) 的原根当且仅当 \(a^0,a^1,\cdots,a^{\varphi(n)−1}\) 在 \(\mod n\) 意义下两两不同

这也是原根重要的性质和等价定义

模 \(n\) 存在原根当且仅当 \(n = 1, 2, 4, p^k , 2p^k\)，其中 \(p\) 为素数，\(k\) 为正整数。

离散对数

设 \(g\) 是模 \(n\) 的原根。那么对于任意 \(a\) 满足 \(a\perp n\)，均存在 \(k\) 使 得 \[ g^k\equiv a\pmod n \] 这样的关系有助于把 \(\mod n\) 的乘法转化为 \(\mod \varphi(n)\) 的加法，与对数的作用有相似之处

\(Lucas\) 定理

用 \(\dbinom{n}{k}\) 表示二项式系数

若 \(p\) 是素数，则有： \[ \dbinom nm\equiv\dbinom{n\mod p}{m\mod p}\dbinom{\left\lfloor\frac np\right\rfloor}{\left\lfloor\frac mp\right\rfloor} \pmod p \]

推论

若将 \(n, m\) 都表示为 \(k\) 位的 \(p\) 进制数，即 \[ n=\sum_{i=0}^{k-1}n_i\cdot p^i\\ m=\sum_{i=0}^{k-1}m_i\cdot p^i \] 那么有 \[ \dbinom nm\equiv\prod_{i=1}^{k-1}\dbinom{n_i}{m_i} \pmod p \] ## 组合数取模

如何求 \(\dbinom{n}{m} \mod p\;\)

如果 \(n, m < p\)，我们可以预处理 \(0\) 到 \(n − 1\) 的阶乘及他们模 \(p\) 的逆元，就可以 \(O(1)\) 计算一个组合数

否则利用 \(Lucas\) 定理递归的计算

附件下载