「笔记」数论相关复习

目录

• 简介
• 更新日志
• 逆元
• 最大公约数
• 素数
• 斐蜀定理$^{[2]}$
• 扩展欧几里得（exgcd）$^{[3]}$
• 欧拉函数$^{[4]}$$^{[5]}$
• 欧拉定理$^{[5]}$
• Miller-Rabin 素数测试$^{[6]}$
• BSGS$^{[7]}$$^{[8]}$
• 中国剩余定理（CRT）
• 扩展中国剩余定理（exCRT）
• 大数翻倍法
• 阶和原根
  • 阶 ord
  • 原根 Origin root
• 二次剩余
  • 定义
  • 解的数量
  • 勒让德符号
  • 欧拉判别准则
  • Cipolla 算法
• 范德蒙德卷积

简介

主要涉及数论方面的复习（大概是 NOIP 难度），目的为复习使用，因此与其他博客相比会更为简略，想要更详细的介绍也附上了相应的链接。

仅供大家参考，如有错误请指出。

内容太简单，大佬不要喷啊。>-<

先发一部分，后面的会慢慢补。

建议配合食用。

更新日志

• upd on 2021.8.31： 完成初稿。
• upd on 2021.9.1 ： 学习并补充了阶和原根，二次剩余。
• upd on 2021.9.9 ： 添加范德蒙德卷积

逆元

求 \(ax \equiv 1 \pmod p\)

根据费马小定理有（\(p\) 为质数）：

\[a \equiv x^{p-2} \pmod p \]

线性求逆元：

\[i^{-1} = (p - \left\lfloor \frac{p}{i} \right\rfloor) \times (p\bmod i)^{-1} \pmod p \]

最大公约数

int Gcd(int x, int y) { return !y ? x : Gcd(y, x % y); }

素数

暴力：\(O(\sqrt n)\) 判断单个 \(x\) 是否为素数。
埃氏筛：\(O(n \log n)\) 判断 \([1 \sim n]\) 是否为素数。
欧拉筛：\(O(n)\) 判断 \([1 \sim n]\) 是否为素数。

// 只给线筛。
int tmp[MAXN], Cnt = 0;
bool vis[MAXN];
void Init(int limit) {
    for(int i = 2; i <= limit; ++i) {
        if(!vis[i]) tmp[++ Cnt] = i;
        for(int j = 1; j <= Cnt && i * tmp[j] <= limit; ++j) {
            vis[i * tmp[j]] = true;
            if(i % tmp[j] == 0) break;
        }
    }
}

斐蜀定理

设 \(d = \gcd(a, b)\)，那么对于方程 \(ax + by = d\) ，一定存在一组整数解。并且对于方程 \(ax + by = z\)，如果满足 \(d \mid z\)，那么方程一定有整数解，否则无整数解。

如何遍历所有解？

另外的，可以看出 \(x, y\) 的解不是唯一的，有无穷组系数 \((x, y)\) 都能满足 \(\gcd(a, b) = ax + by\)。并且，如果 \((x, y)\) 是一组系数，那么所有系数可以表示为

\[(x + k · \frac{b}{\gcd(a,b)}, y - k·\frac{a}{\gcd(a,b)} ) \mid k \in \mathbb{Z} \]

扩展欧几里得（exgcd）

已知 \(a,b\)，求 \(ax+by = \gcd(a,b)\) 的一组解。

int Exgcd(int a, int b, int &x, int &y) {
    if(!b) { x = 1, y = 0; return a; }
    int d = Exgcd(b, a % b, x, y);
    int t = x;
    x = y, y = t - a . b * y;
    return d;
}

欧拉函数

通常计作 \(\varphi (n)\)，表示小于 \(n\) 且与 \(n\) 互质的数的个数。

当 \(n\) 是质数时，\(\varphi(n) = n-1\)。

欧拉函数是一个积性函数。当 \(\gcd(n,m)=1\) 时，\(\varphi (n \times m) = \varphi(n)\varphi(m)\)。

欧拉函数的通项公式：

\[\varphi(n) = n \times \displaystyle \prod_{i=1}^{k} (1- \frac{1}{p_i}) \]

欧拉定理

当 \(a\) 与 \(p\) 互质时有 \(a^{\varphi(p)} \equiv 1 \pmod p\)。

同时有一个引理 \(a^{2\varphi(p)} \equiv a^{\varphi(p)} \pmod p\)。

然后推广它：

\[a^{p} \equiv a^{p \!\!\!\mod \!\! {\varphi (p)}} \pmod p \]

Miller-Rabin 素数测试

我们知道素数可以表示成这种形式 \(n = d \times 2^r + 1\) ，（当然，需要特判 \(2\)）。

只要这个数满足下面两个条件中的一个，就可以通过素数测试：

\[\begin{cases} a^d \equiv 1 \pmod n \\ \exists \ \ 0 \leq i < r , a^{d \times 2^{i}} \equiv -1 \pmod n \end{cases}\]

其中 \(a\) 是我们选择的一个小质数，在 \(100\) 选择 \(8 \sim 12\) 个就基本能保证正确性。

如果一个数是素数，一定会通过素数测试；如果一个数是合数，很大概率不会通过素数测试。

复杂度应该是 \(O(k\log^2 n)\)，因为需要枚举一个 \(r\)，还有龟速乘。\(k\) 是选取的 \(a\) 的数量。

// Quick_Pow 是快速幂，Quick_Mul 是龟速乘。
bool Miller_Rabin(int n, int a) {
    int d = n - 1, r = 0;
    while(d % 2 == 0) ++r, d >>= 1;
    int x = Quick_Pow(a, d, n);
    if(x == 1) return true;
    for(int i = 0; i < r; ++i) {
        if(x == n - 1) return true;
        x = Quick_Mul(x, x, n); 
    }
    return false;
}

int prim_list[] = {2, 3, 5, 7, 23, 37, 47, 83, 97};
bool Prime(int n) {
    if(n < 2) return false;
    for(int i = 0; i < 9; ++i) {
        if(n == prim_list[i]) return true;
        if(n % prim_list[i] == 0) return false;
        if(Miller_Rabin(n, prim_list[i]) == false) return false;
    }
    return true;
}

例题：SP288

BSGS\(^{[7]}\)\(^{[8]}\)

求解最小的满足下面条件的 \(x\)，保证 \(a \bot p\)。

\[a^x \equiv b \pmod p \]

设 \(t = i \times \left \lceil \sqrt p \right \rceil - j\)，\(1 \le i,j \le \sqrt p\)，然后两边同乘 \(a^j\)，有

\[a^{i \times t} \equiv ba^j \pmod p \]

考虑所有 \(j \in [0,t-1]\)，求出 \(ba^j\) 并把他们放入哈希表，然后枚举 \(i\) 查找有无这个值，这样我们就能求出一个合法的 \(x\)，取最小值即可。

复杂度 \(O(\sqrt p)\)，使用 map 会带一个 \(\log\)。（所以说这个算法处理不了 \(10^{18}\) 级别的数据）

int BSGS(int a, int b, int p) {
    map Hash; Hash.clear();
    b %= p;
    int t = sqrt(p) + 1;
    for(int i = 0; i < t; ++i) Hash[b * Pow(a, i, p) % p] = i; // 存储 hash 值 
    a = Pow(a, t, p);
    if(!a) return b == 0 ? 1 : -1;
    for(int i = 1; i <= t; ++i) { // 看看能不能找到 
        int val = Pow(a, i, p);
        int j = (Hash.find(val) == Hash.end()) ? -1 : Hash[val];
        if(j >= 0 && i * t - j >= 0) return i * t - j; // 首先找到的一定是最小的。 
    }
    return -1;
}

BSGS例题及题解

中国剩余定理（CRT）

用于求解线性同余方程，在模数互质的情况下适用。

扩展中国剩余定理（exCRT）

用于求解线性同余方程，模数互质不互质均适用。

详细见这篇博客。

大数翻倍法

一种暴力的，求解线性同余方程的方法。码量和理解难度都很小。

阶和原根

阶 ord

由欧拉定理可知，对 \(a \in \mathbb Z, m \in \mathbb N^*\)，若 \(\gcd (a,m) = 1\)，则 \(a^{\varphi(m)} \equiv 1 \pmod m\)。

因此满足同余式 \(a^x \equiv 1 \pmod m\) 的最小正整数 \(x\) 存在，这个 \(x\) 称作 \(a\) 模 \(n\) 的阶，计作 \(\delta_m(a)\)。

几个性质：

• 1、\(a,a^2,...,a^{\delta_m(a)}\) 模 \(m\) 两两不同余。
• 2、若 \(a^n \equiv 1 \pmod m\) ，则 \(\delta_m(a) \mid n\)。
• 3、由 2 可以推出，如果 \(a^p \equiv a^q \pmod m\) 那么 \(p \equiv q \pmod {\delta_m(a)}\)。
• 4、设 \(m \in \mathbb N^*\)，\(a,b \in \mathbb Z\),\(\gcd(a,m) = \gcd(b,m) = 1\)，则

\[\delta_m(a,b) = \delta_m(a) \delta_m(b) \]

的充分必要条件是

\[\gcd(\delta_m(a),\delta_m(b)) = 1 \]

• 5、设 \(k \in \mathbb N\)，\(m \in \mathbb N^*\)，\(a \in \mathbb Z\)，\(\gcd(a,m) = 1\)，则

\[\delta_m(a^k) = \frac{\delta_m(a)}{\gcd(\delta_m(a),k)} \]

详细证明见这篇博客。

原根 Origin root

定义：

设 \(m \in \mathbb N^*\)，\(a \in \mathbb Z\)。若 \(\gcd(a,m) = 1\)，且 \(\delta_m(a) = \varphi(m)\)，则称 \(a\) 为模 \(m\) 的原根。

原根判定定理：

设 \(m \ge 3, \gcd(a,m) = 1\)，则 \(a\) 是模 \(m\) 的原根的充要条件是，对于 \(\varphi (m)\) 的所有素因数 \(p\)，都满足 \(a^{\frac{\varphi(m}{p}} \not\equiv 1 \pmod m\)

原根个数：

若一个数有原根，则它的原根个数为 \(\varphi (\varphi(m))\)。

原根存在定理：

一个数 \(m\) 存在原根当且仅当 \(m=2,4,p^{\alpha},2p^{\alpha}\)，其中 \(p\) 是奇素数，\(\alpha \in \mathbb N^*\) 。

几个用来证明原根存在的定理：

• 定理 1：对于奇素数 \(p\) ，\(p\) 有原根。
• 引理：设 \(a\) 与 \(b\) 是与 \(p\) 互素的两个整数，则存在 \(c \in \mathbb Z\) 使得 \(\delta_p(c) = \operatorname {lcm} (\delta_p(a),\delta_p(b))\)，
• 定理 2：对于奇素数 \(p\)，\(\alpha \in \mathbb Z\)，\(p^{\alpha}\) 有原根。
• 引理：存在模 \(p\) 的原根 \(g\)，使得 \(g^{p-1} \not\equiv 1 \pmod {p^2}\)
• 对于奇素数 \(p\)，\(\alpha \in \mathbb N^*\)，\(2p^{\alpha}2\) 的原根存在。
• 对于 \(m \not= 2,4\) 且不存在奇素数 \(p\) 及 \(\alpha \in \mathbb N^*\) 使得 \(m = p^{\alpha},2p^{\alpha}\)，模 \(m\) 的原根不存在。

最小原根的数量级：

王元在 \(1959\) 年证明了，若 \(m\) 有原根，其最小原根是不多于 \(m^{0.25}\) 级别的。（这启发我们可以暴力找最小原根）

详细证明见这篇博客。

[模板][题解][代码]

二次剩余

定义

一个数 \(a\)，如果不是 \(p\) 的倍数且模 \(p\) 同余于某个数的平方，则称 \(a\) 为模 \(p\) 的 二次剩余。而一个不是 \(p\) 的倍数的数 \(b\)，不同余于任何数的平方，则称 \(b\) 为模 \(p\) 的 非二次剩余。

对二次剩余求解，也就是对常数 \(a\) 解下面的这个方程：

\[x^2 \equiv a \pmod p \]

通俗一些，可以认为是求模意义下的开方。

只会 \(p\) 为奇素数的算法，\(\text{Cipolla}\) 算法。

解的数量

对于 \(x^2 \equiv n \pmod p\)，能满足＂\(n\) 是模 \(p\) 的二次剩余＂的 \(n\) 一共有 \(\frac{p-1}{2}\) 个（0 不包括在内），非二次剩余有 \(\frac{p-1}{2}\) 个。

勒让德符号

\[\left(\frac{n}{p}\right)=\begin{cases} 1,\,& p\nmid n \text{且}n\text{是}p\text{的二次剩余}\\ -1,\,& p\nmid n \text{且}n\text{不是}p\text{的二次剩余}\\ 0,\,& p\mid n \end{cases} \]

欧拉判别准则

\[(\frac{n}{p}) \equiv n^{\frac{p-1}{2}} \pmod p \]

若 \(n\) 是二次剩余，当且仅当 \(n^{\frac{p-1}{2}} \equiv 1 \pmod p\)。

若 \(n\) 是非二次剩余，当且仅当 \(n^{\frac{p-1}{2}} \equiv -1 \pmod p\)。

Cipolla 算法

找到一个数 \(a\) 满足 \(a^2-n\) 是 非二次剩余，至于为什么要找满足非二次剩余的数，在下文会给出解释。 这里通过生成随机数再检验的方法来实现，由于非二次剩余的数量为 \(\frac{p-1}{2}\)，接近 \(\frac{p}{2}\)，所以期望约 2 次就可以找到这个数。

建立一个＂复数域＂，并不是实际意义上的复数域，而是根据复数域的概念建立的一个类似的域。 在复数中 \(i^2 = -1\)，这里定义 \(i^2 = a^2 - n\)，于是就可以将所有的数表达为 \(A+Bi\) 的形式，这里的 \(A\) 和 \(B\) 都是模意义下的数，类似复数中的实部和虚部。

在有了 \(a\) 和 \(i\) 后可以直接得到答案，\(x^2 \equiv n \pmod p\) 的解为 \((a+i)^{\frac{p+1}{2}}\)。

详细证明见这篇博客。

[模板][代码]

范德蒙德卷积

形似：

\[\sum_{i=0}^k\binom {n}{i} \binom {m}{k-i} = \binom {n+m}{k} \]

可以理解为在大小为 \(n\) 和 \(m\) 的两个堆中选择 \(k\) 个点的方案数

推论：

\[\sum_{i=1}^n\binom ni\binom {n}{i-1}=\binom {2n}{n-1} \]

感觉比较显然，把前面一个组合数转化成 \(\binom {n}{n-i}\) 在利用上面的结论就行了。

其他的推论：

\[\sum_{i=0}^n\binom ni^2=\sum_{i=0}^n\binom ni\binom n{n-i}=\binom {2n}n\\\sum_{i=0}^m\binom ni\binom mi=\sum_{i=0}^m\binom ni\binom m{m-i}=\binom {n+m}m \]