简介
主要涉及数论方面的复习（大概是 NOIP 难度），目的为复习使用，因此与其他博客相比会更为简略，想要更详细的介绍也附上了相应的链接。
仅供大家参考，如有错误请指出。
内容太简单，大佬不要喷啊。>-<
先发一部分，后面的会慢慢补。
建议配合数论做题记录食用。
更新日志
- upd on 2021.8.31： 完成初稿。
- upd on 2021.9.1 ： 学习并补充了阶和原根，二次剩余。
- upd on 2021.9.9 ： 添加范德蒙德卷积
逆元
求 (ax equiv 1 pmod p)
根据费马小定理有（(p) 为质数）：
线性求逆元(^{[1]})：
最大公约数
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;
}
}
}
斐蜀定理(^{[2]})
设 (d = gcd(a, b))，那么对于方程 (ax + by = d) ，一定存在一组整数解。并且对于方程 (ax + by = z)，如果满足 (d mid z)，那么方程一定有整数解，否则无整数解。
如何遍历所有解？
另外的，可以看出 (x, y) 的解不是唯一的，有无穷组系数 ((x, y)) 都能满足 (gcd(a, b) = ax + by)。并且，如果 ((x, y)) 是一组系数，那么所有系数可以表示为
扩展欧几里得（exgcd）(^{[3]})
已知 (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;
}
欧拉函数(^{[4]})(^{[5]})
通常计作 (varphi (n))，表示小于 (n) 且与 (n) 互质的数的个数。
当 (n) 是质数时，(varphi(n) = n-1)。
欧拉函数是一个积性函数。当 (gcd(n,m)=1) 时，(varphi (n imes m) = varphi(n)varphi(m))。
欧拉函数的通项公式：
欧拉定理(^{[5]})
当 (a) 与 (p) 互质时有 (a^{varphi(p)} equiv 1 pmod p)。
同时有一个引理 (a^{2varphi(p)} equiv a^{varphi(p)} pmod p)。
然后推广它：
Miller-Rabin 素数测试(^{[6]})
我们知道素数可以表示成这种形式 (n = d imes 2^r + 1) ，（当然，需要特判 (2)）。
只要这个数满足下面两个条件中的一个，就可以通过素数测试：
其中 (a) 是我们选择的一个小质数，在 (100) 选择 (8 sim 12) 个就基本能保证正确性。
如果一个数是素数，一定会通过素数测试；如果一个数是合数，很大概率不会通过素数测试。
复杂度应该是 (O(klog^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 ot p)。
设 (t = i imes left lceil sqrt p ight ceil - j)，(1 le i,j le sqrt p)，然后两边同乘 (a^j)，有
考虑所有 (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<int, int> 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;
}
中国剩余定理（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)，则
的充分必要条件是
- 5、设 (k in mathbb N)，(m in mathbb N^*)，(a in mathbb Z)，(gcd(a,m) = 1)，则
原根 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}} otequiv 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} otequiv 1 pmod {p^2})
- 对于奇素数 (p)，(alpha in mathbb N^*)，(2p^{alpha}2) 的原根存在。
- 对于 (m ot= 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) 解下面的这个方程：
通俗一些，可以认为是求模意义下的开方。
只会 (p) 为奇素数的算法，( ext{Cipolla}) 算法。
解的数量
对于 (x^2 equiv n pmod p)，能满足＂(n) 是模 (p) 的二次剩余＂的 (n) 一共有 (frac{p-1}{2}) 个（0 不包括在内），非二次剩余有 (frac{p-1}{2}) 个。
勒让德符号
欧拉判别准则
若 (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}})。
范德蒙德卷积
形似：
可以理解为在大小为 (n) 和 (m) 的两个堆中选择 (k) 个点的方案数
推论：
感觉比较显然，把前面一个组合数转化成 (inom {n}{n-i}) 在利用上面的结论就行了。
其他的推论：