目录
- 数论
数论
模运算相关
龟速乘
乘法取余。
时间复杂度 \(O(\log b)\)
空间复杂度 \(O(1)\)
const int P = 1e9 + 7;
ll qmul(ll a, ll b) {
ll ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % P;
b >>= 1;
a = (a << 1) % P;
}
return ans;
}
快速幂
幂取余，\(a\) 越大速度越慢。
时间复杂度 \(O(\log k)\)
空间复杂度 \(O(1)\)
const int P = 1e9 + 7;
ll qpow(ll a, ll k) {
ll ans = 1;
while (k) {
if (k & 1) ans = ans * a % P;
k >>= 1;
a = a * a % P;
}
return ans;
}
矩阵快速幂
矩阵幂取余。
时间复杂度 \(O(n^3 \log k)\)
空间复杂度 \(O(1)\)
const int P = 1e9 + 7;
struct Matrix {
int n, m;//不能const，快速幂要复制
vector<vector<ll>> mat;
explicit Matrix(int _n):n(_n), m(_n), mat(_n + 1, vector<ll>(_n + 1)) {
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
mat[i][j] = i == j;
}//初始化n阶单位矩阵，explicit防止误用类型转换
Matrix(int _n, int _m):n(_n), m(_m), mat(_n + 1, vector<ll>(_m + 1)) {}//初始化nxm零矩阵
friend Matrix operator*(const Matrix &A, const Matrix &B) {
Matrix ans(A.n, B.m);
if (A.m != B.n) return ans;
for (int i = 1;i <= A.n;i++)
for (int j = 1;j <= B.m;j++)
for (int k = 1;k <= A.m;k++) //a.m == b.n
ans.mat[i][j] = (ans.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % P;
return ans;
}//矩阵乘法取余
friend Matrix operator^(Matrix A, ll k) {
Matrix ans(A.n);//A必须是方阵
while (k) {
if (k & 1) ans = ans * A;
k >>= 1;
A = A * A;
}
return ans;
}//快速幂取余
void output() const {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
cout << mat[i][j] << ' ';
cout << '\n';
}
cout << '\n';
}//输出检测
};
整除
整除的定义与性质
定义 设 \(a,b \in \Z\) ，若 \(b\) 除以 \(a\) 余数为 \(0\) ，则称 \(a\) 整除 \(b\) ，记为 \(a \mid b\) 。
设 \(a,b,c \in \Z\) 。
性质1 \(a \mid b \text{ 且 } b \mid c \Rightarrow a \mid c\) 。
性质2 \(a \mid b \Rightarrow a \mid kb\) ，\(k \in \Z\) 。
性质3 \(a \mid b \text{ 且 } a \mid c \Rightarrow a \mid kb + lc\) ， \(k,l\in \Z\) 。
性质4 \(a \mid b \text{ 且 } b \mid a \Rightarrow a = \pm b\) 。
性质5 \(a = kb \pm c \Rightarrow a,b \text{ 的公因数与 } b,c \text{ 的公因数相同}\) 。
性质6 \(a \mid bc \text{ 且 } \gcd (a,c) = 1 \Rightarrow a \mid b\) 。
素数
素数的定义与性质
定义 素数（质数）是只有 \(1\) 和它本身两个因数的数，否则为合数。
约定 \(1\) 既不是素数，也不是合数。
偶素数 \(2\) 是唯一的偶素数。
素数定理
设 \(\pi(n)\) 为 \([1,n]\) 中素数的个数。
素数分布存在渐进， \(\pi(n) \sim \dfrac{n}{\ln n},n \rightarrow \infty\) 。
由素数定理，可以得到如下定理：
定理1 对于 \(n \in \N^+\) ，有 \(\pi(n) \approx \dfrac{n}{\ln n}\) 。
定理2（伯特兰-切比雪夫定理） 对于任意整数 \(n\geq 4\) ，存在质数 \(p\) 满足 \(n < p < 2n-2\) 。
定理2的推论 对于任意整数 \(n\geq 2\) ，存在质数 \(p\) 满足 \(n < p < 2n\) 。
素数判定
试除法
一个数 \(n\) 若是合数，则一定在 \([1,\sqrt n]\) 中存在一个质数整除 \(n\) 。
证明：
设 \(d\) 是 \(n\) 的一个质因子，则 \(\dfrac{n}{d}\) 也能整除 \(n\) 。假设 \(d \leq \dfrac{n}{d}\) ，则 \(d \leq \sqrt{n}\) 。
时间复杂度 \(O(\sqrt n)\)
空间复杂度 \(O(1)\)
bool isPrime(int n) {
if (n == 2) return 1;
if (n == 1) return 0;
for (int i = 2;i * i <= n;i++) if (!(n % i)) return 0;
return 1;
}
\(kn+i\) 法
试除法的升级版，常数更小。
一个数 \(n\) 若是合数，则一定存在 \([1,\sqrt n]\) 的质因子。因此，在试除法的基础上，枚举因子时只考虑可能成为质因子的因子。
例如 \(k = 30\) 时，只有 \(i = 1,7,11,13,17,19,23,29\) 时的数才有可能成为质因子，其他情况都与 \(30\) 有非 \(1\) 的公因子一定不是素数。如此，算法计算量变为原来的 \(\frac{4}{15}\) 。
\(k = 30\) 时，时间复杂度 \(O(\frac{4}{15} \sqrt n)\)
空间复杂度 \(O(1)\)
bool isPrime(int n) {
if (n == 2 || n == 3 || n == 5) return 1;
if (n == 1 || !(n % 2) || !(n % 3) || !(n % 5)) return 0;
int a[8] = { 4,2,4,2,4,6,2,6 }, p = 0;
for (int i = 7;i * i <= n;i += a[p++], p %= 8) if (!(n % i)) return 0;
return 1;
}
预处理法
欧拉筛 \(O(n)\) 预处理所有素数后，试除法可以直接枚举质因子。
根据素数定理，素数占比约为 \(\frac{1}{\ln n}\) ，因此复杂度变为原来的 \(\frac{1}{\ln n}\)。
时间复杂度 \(O(\frac{\sqrt n}{\ln n})\)
空间复杂度 \(O(n)\)
Miller-Rabin素性测试
Miller-Rabin素性测试通常用于判定大数（远超 \(2^{64}\) 范围）是否为素数，其是费马素性测试的改进版。
众所周知，费马小定理：
当 \(a\) 不是 \(p\) 的倍数，若 \(p\) 为素数，则 \(a^{p-1} \equiv 1 \pmod p\) 。
但其逆命题：
当 \(a\) 不是 \(p\) 的倍数，若 \(a^{p-1} \equiv 1 \pmod p\) ，则 \(p\) 为素数。
并不总是成立。例如，\(2^{341-1} \equiv 1 \pmod{341},3^{1105-1} \equiv 1 \pmod{1105}\) ，这些数称为费马伪素数。
但事实上，费马伪素数的概率并不是很大。我们可以对一个数 \(p\) 取 \(k\) 个 \(a\) 测试，若存在 \(a^{p-1} \not\equiv 1 \pmod p\) ，则 \(p\) 一定是合数；否则，\(p\) 很大概率是素数。这个过程称为费马素性测试，时间复杂度为 \(O(k \log n)\) 。可惜的是，到 long long 范围，费马素性测试的准确性就已经开始不高了。因此，在此基础上有了改进的算法Miller-Rabin素性测试 。
Miller-Rabin素性测试在费马素性测试的基础上增加了二次探测定理的使用。二次探测定理：
若 \(p\) 为奇素数，则 \(x^2 \equiv 1 \pmod p\) 的解为 $x \equiv \pm 1 \pmod{p} $ 。特别地，在 \([0,p-1]\) 的解为 \(x = 1\) 或 \(x = p-1\) 。
因为只能探测奇素数，所以偶数要开始前判掉。
我们先将 \(p-1\) 拆分为 \(2^rm\) （\(m\) 为奇数，\(r \geq 1\) ），随后考虑对 \(x = a^m,a^{2m},\cdots,a^{2^{r-1}m}\) 进行二次探测。根据费马素性测试，这个 \(x\) 序列探测到最后的结果应是 \(1\) 。我们对出现 \(1\) 的情况分类讨论：
- 如果一开始 \(a^{m} \equiv \pm 1 \pmod p\) 成立，后续探测全是 \(x^2 \equiv 1 \pmod p\) 就不需要判断了。
- 若不成立，则一定要在 \(r-1\) 次探测内先得到 \(x^2 \equiv - 1 \pmod p\) ，否则最后一定出现结果不为 \(1\) 或者出现 \(x^2 \equiv 1 \pmod p\) 但 \(x \not \equiv \pm 1 \pmod p\) 的情况，则 \(p\) 为合数。
判定大数 \(n\) 是否为素数的具体步骤：
- 特判 \(n=1,2\) 以及其他所有偶数。
- 将 \(n-1\) 拆分成 \(2^rm\) ，若 \(a^{m} \equiv \pm 1 \pmod{n}\) ，则后续全是 \(1\) 不需要判断，否则下一步。
- 枚举 \(k\) 个（通常为 \(8\) 到 \(10\) 个） \(a \in [1,n-1]\) 保证不是 \(n\) 的倍数，对 \(x = a^m,a^{2m},\cdots,a^{2^{r-2}m}\) 进行共 \(r-1\) 次二次探测，是否经过 \(-1\) 。
- 若 \(k\) 次测试都通过，则 \(n\) 大概率为素数；某次没通过就一定是合数。
时间复杂度 \(O(k \log n)\)
空间复杂度 \(O(1)\)
namespace Miller_Rabin {
template<class T>
T randint(T l, T r) {
static mt19937 eng(time(0));
uniform_int_distribution<T> dis(l, r);
return dis(eng);
}
ll qpow(ll a, ll k, ll P) {
ll ans = 1;
while (k) {
if (k & 1) ans = (__int128_t)ans * a % P;
k >>= 1;
a = (__int128_t)a * a % P;
}
return ans;
}
bool isPrime(ll n, int k = 10) {//8-10次
if (n == 2) return 1;
if (n == 1 || !(n & 1)) return 0;
ll r = __builtin_ctzll(n - 1);
ll m = n - 1 >> r;
while (k--) {
ll x = qpow(randint(1LL, n - 1), m, n);
if (x == 1 || x == n - 1) continue;//直接满足,否则r-1次内必须有n-1
for (ll i = 1;i <= r - 1 && x != 1 && x != n - 1;i++) x = (__int128_t)x * x % n;//二次探测
if (x != n - 1) return 0;//未经过n-1
}
return 1;
}
}
素数筛法
埃氏筛
素数的倍数一定是合数，合数的倍数一定被某个质因子的倍数筛掉了，因此我们只需要筛掉素数的倍数。
在 \(2\times 10^7\) 内，还是能跑到 \(1\) 秒以内的，再大就不行了。
时间复杂度 \(O(n \log \log n)\)
空间复杂度 \(O(n)\)
const int N = 1e7 + 7;
bool vis[N];
vector<int> prime;
void get_prime(int n) {
for (int i = 2;i <= n;i++) {
if (vis[i]) continue;
prime.push_back(i);
for (int j = 2;j * i <= n;j++) vis[i * j] = 1;
}
}
欧拉筛（线性筛）
埃氏筛的时间复杂度已经很优秀了，但依旧会造成一个合数被筛多次的情况，我们希望每个合数都只被筛一次。因此，我们有欧拉筛，每个合数只会被其最小质因子筛掉。
证明：
假设对于 \(i \in [2,n]\) 的每个数，设其最小质因子为 \(p\) ，我们只筛到其 \(p\) 倍。
先证明任意合数 \(n\) 都能被最小质因子筛一次。
任意合数 \(n\) ，设其最小质因子为 \(p'\) ，则 \(i = \dfrac{n}{p’}\) ，那么有 \(p' \leq p\) ，因此 \(n\) 一定能在 \(i\) 的 \(p\) 倍时或者之前被其最小质因子 \(p'\) 筛掉。
再证明任意合数 \(n\) 不会被非最小质因子筛掉。
任意合数 \(n\) ，设其最小质因子为 \(p'\) ，其他任意质因子为 \(p''\)， 有 \(p'' > p'\) ，则 \(i = \dfrac{n}{p''}\) 的最小质因子 \(p = p' < p''\) ，因此 \(n\) 根本不会被某个数的 \(p''\) 倍筛掉。
因此，我们对每个数只筛到其最小质因子倍，就能保证筛掉的每个数只会被其最小质因子筛一次。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
const int N = 1e7 + 7;
bool vis[N];
vector<int> prime;
void get_prime(int n) {
for (int i = 2;i <= n;i++) {
if (!vis[i]) prime.push_back(i);
for (int j = 0;j < prime.size() && i * prime[j] <= n;j++) {
vis[i * prime[j]] = 1;
if (!(i % prime[j])) break;
}
}
}
反素数
反素数的定义与性质
定义 对于正整数 \(n\) ，满足任何小于 \(n\) 的数的因子个数都小于 \(n\) 的因子个数。
性质1 \([1,n]\) 中的反素数，一定是相同因子个数的数中最小的。
显然对于任意 \(n \in [1,2^{31}]\) ，其质因子不会超过 \(10\) 个，且质因子的指数之和不会超过 \(31\) 。
性质2 当 \(x \in [1,n],n\leq 2^{31}\) ，则 \(x\) 是反素数的必要条件是 \(x = 2^{c_1} \times 3^{c_2} \times 5^{c_3} \times 7^{c_4} \times 11^{c_5} \times 13^{c_6} \times 17^{c_7} \times 19^{c_8} \times 23^{c_9} \times 29^{c_{10}}\) ，其中 \(c_1 \geq c_2 \geq \cdots \geq c_{10} \geq 0\) 。
枚举反素数
根据性质2，我们可以通过dfs枚举每个质因子的指数，进而求出可能为反素数的数。再求其因子个数，根据性质1，取相同因子个数中最小的那个数即可筛选出所有反素数。
正整数结构
唯一分解定理
任何一个大于 \(1\) 的整数都可以被分解为有限个素数的乘积：
\[n = \prod_{i=1}^m p_i^{c_i} = p_1^{c_1} \times p_2^{c_2} \times \cdots \times p_m^{c_m} \]其中 \(p_1 < p_2 < \cdots < p_m\) 为质数，\(c_i \in \Z^*\) 。
质因子分解
试除法
枚举 \(i \in [2,\sqrt n]\) ，一个一个除尽质因子。当然，最后至多留一个 \(> \sqrt n\) 的质因子，需要特判。
质因子不会太多（最多几十个），所以空间当作常数。
时间复杂度 \(O(\sqrt n)\)
空间复杂度 \(O(1)\)
提前 \(O(n)\) 预处理素数
时间复杂度 \(O(\frac{\sqrt n}{\ln n})\)
空间复杂度 \(O(n)\)
vector<pair<int, int>> pfact;
void get_pfact(int n) {
for (int i = 2;i * i <= n;i++) {
if (!(n % i)) pfact.push_back({ i,0 });
while (!(n % i)) n /= i, pfact.back().second++;
}
if (n > 1) pfact.push_back({ n,1 });//最后可能留一个大于sqrt(n)的质数
}
Pollard-Rho算法
Pollard-Rho算法适用于快速随机找到大数的一个非 \(1\) 因子。基于这个算法，我们可以利用递归快速分解一个大数的质因子，时间复杂度大约相同。
普通试除法的时间复杂度是 \(O(\sqrt n)\) ，对于 long long 范围的大数是不可接受的。
Pollard-Rho的想法产生于生成随机数 \(m \in [2,n-1]\) ，测试 \(\gcd (m,n) = d > 1\) ，来产生因子 \(d\) 的算法。但这种算法的期望复杂度是 \(O(\sqrt n \log n)\) ，比试除法还差，因此Pollard考虑利用生日悖论对随机数作差来碰撞因子。
生日悖论：
在一年有 \(n\) 天的情况下，当房间中约有 \(\sqrt{2n\ln 2}\) 个人时，至少有两个人的生日相同的概率约为 \(50 \%\) 。
更进一步地说，我们在 \([1,n]\) 内随机生成数字，产生第一个重复数字前期望有 \(\sqrt {\dfrac{\pi n}{2}}\) 个数，约为 \(\sqrt n\) 个。
因此，假设 \(n\) 有非 \(1\) 因子 \(d\) ，我们从 \([1,n-1]\) 期望随机抽取 \(\sqrt d\) 个数字后，就能产生两个数 \(i,j\) 满足 \(i - j \equiv 0 \pmod d\) ，即 \(\gcd(i-j,n) = d > 1\) 。所以，产生这样一对数字的期望最差复杂度是 \(O(n^{\frac{1}{4}})\) ，但为了找到这些数字，需要大量互相作差并求 \(\gcd\) ，因此复杂度又回到 \(\sqrt n \log n\) 。
Pollard为了避免这种情况，构造了一种伪随机序列 \(x_n = (x_{n-1}^2 + c) \mod n\) ，其中起点 \(x_0\) 和常数 \(c\) 是随机在 \([1,n-1]\) 中给定的。这样的作用是，假设 \(n\) 有非 \(1\) 因子 \(d\) ，且序列存在一组数字 \(x_i,x_j\) 满足 \(x_i - x_j \equiv 0 \pmod d\) ，那么 \(x_{i+1} - x_{j+1} \equiv x_i^2 - x_j^2 \equiv (x_i-x_j)(x_i+x_j) \equiv 0 \pmod d\) ，即未来所有距离为 \(i-j\) 的数的差都会产生因子 \(d\) 。
因为这组伪随机序列是模 \(n\) 的，因此一定会产生一个混循环（这也是为什么叫做 \(\text{Rho} \to \rho\) ），所以在环上测一组，相当于测了环上所有组距离 \(i-j\) 的数，于是就不需要两两测试了，期望测 \(n^{\frac{1}{4}}\) 组就够了。
此时期望复杂度是 \(O(n^{\frac{1}{4}} \log n)\) ，我们还希望把 \(\log\) 去掉，因此有了倍增优化。倍增优化的原理是：
若 \(\gcd (m,n) = d > 1\) ，则 \(\gcd(km,n)\geq d,k\in \Z^*\) 。
这意味着我们可以累积计算 \(1,2,4,8,\cdots\) 次差，乘在一起求 \(\gcd\) ，若某次作差产生非 \(1\) 因子，那么乘积一定会产生非 \(1\) 因子，时间复杂度为 \(O(n^{\frac{1}{4}} + \log(n^{\frac{1}{4}})\log n)\) 。但是缺点是，我们倍增到最后可能由于单次积累量太大直接超过期望值太多反而变慢。实际上，我们不需要倍增多少次，假设我们取 \(dis\) 作为一次累积的量，那么复杂度为 \(O(n^{\frac{1}{4}} + \frac{n^{\frac{1}{4}}\log n}{dis})\) ，只要 \(dis \geq \log n\) 就能做到复杂度 \(O(n^{\frac{1}{4}})\) 。在 long long 范围内我们令 \(dis = 128\) 就足够了，我们在倍增的基础上每隔 \(128\) 次检测一次即可，不到 \(128\) 次则在结束时检测。
还有一种优化，Floyd判环算法，用于在进入循环时及时退出不重复跑圈。我们设两个数 \(x,y\) ，每次判断 \(\gcd(|x-y|,n)>1\) ，若没有则令 \(x\) 走一步，\(y\) 走两步。因为每次 \(y\) 多走一步，如果进入环则 \(y\) 一定能追上 \(x\) ，此时退出即可。
但实际上，判环算法的优化是不如倍增算法的（时间大约多一倍），且两者不太好兼容，因此我们一般使用倍增算法，而不使用判环算法。
拥有了Pollard-Rho算法，我们就可以对大数 \(n\) 进行质因子分解，时间复杂度大约也是 \(O(n^{\frac{1}{4}})\) ：
- 用Miller-Rabin算法判断 \(n\) 是否为素数，如果是直接返回，否则进行下一步。
- 每次用Pollard-Rho算法获得一个非 \(1\) 的因子 \(d\) ，如果为 \(n\) 就再求一次。
- 将数分解为 \(\frac{n}{d}\) 和 \(d\) 两个数，回到第一步递归进行。
时间复杂度 \(O(n^\frac{1}{4})\)
空间复杂度 \(O(1)\)
namespace Miller_Rabin {
template<class T>
T randint(T l, T r) {
static mt19937 eng(time(0));
uniform_int_distribution<T> dis(l, r);
return dis(eng);
}
ll qpow(ll a, ll k, ll P) {
ll ans = 1;
while (k) {
if (k & 1) ans = (__int128_t)ans * a % P;
k >>= 1;
a = (__int128_t)a * a % P;
}
return ans;
}
bool isPrime(ll n, int k = 10) {//8-10次
if (n == 2) return 1;
if (n == 1 || !(n & 1)) return 0;
ll r = __builtin_ctzll(n - 1);
ll m = n - 1 >> r;
while (k--) {
ll x = qpow(randint(1LL, n - 1), m, n);
if (x == 1 || x == n - 1) continue;//直接满足,否则r-1次内必须有n-1
for (ll i = 1;i <= r - 1 && x != 1 && x != n - 1;i++) x = (__int128_t)x * x % n;//二次探测
if (x != n - 1) return 0;//未经过n-1
}
return 1;
}
}
namespace Pollard_Rho {
using namespace Miller_Rabin;
ll one_factor(ll n) {
ll s, x = randint(1LL, n - 1), c = randint(1LL, n - 1), dis = 1, prod = 1;
while (1) {
s = x;//固定起点作差
for (int i = 1;i <= dis;i++) x = ((__int128_t)x * x % n + c) % n;//玄学预循环
for (int i = 1;i <= dis;i++) {
x = ((__int128_t)x * x % n + c) % n;
prod = (__int128_t)prod * abs(x - s) % n;//累积因子
if (i == dis || i % 128 == 0) {//固定最多128次一判
ll d = gcd(prod, n);
if (d > 1)return d;
}
}
dis <<= 1;//路径倍增
}
}
void get_pfactor(ll n, vector<ll> &pfactor) {
if (isPrime(n)) {
pfactor.push_back(n);
return;
}
ll d = n;
while (d >= n) d = one_factor(n);
get_pfactor(n / d, pfactor);
get_pfactor(d, pfactor);
}
}
因数
因数的定义与性质
定义 若整数 \(a,b\) 满足 \(a \mid b\) ，则称 \(a\) 是 \(b\) 的因数（约数，因子），\(b\) 是 \(a\) 的倍数。
我们通常讨论的因数默认为正因数，否则一定会指出。
根据整数唯一分解定理，正整数 \(n\) 可以分解为 \(n = \prod_{i=1}^{m} p_i^{c_i}\) ，其中 \(p_i\) 为质数，\(c_i\) 为正整数，其正因数具有以下性质：
性质1 \(n\) 的正因数有 \(\prod_{i=1}^{m}(c_i+1)\) 个。
性质2 \(n^k,k \in \Z\) 的正因数有 \(\prod_{i=1}^{m}(k \cdot c_i+1)\) 个。
性质3 \(n\) 的正因数和为 \(\prod_{i=1}^{m} \sum_{j=0}^{c_i} p_i^{j}\) 。
性质4 \([1,n]\) 内正因数集合大小约为 \(n \log n\) 。
性质5 \(n\) 的正因数个数期望约为 \(\ln n\) 。