一、质数
1. 定义
如果一个正整数只有 \(1\) 和它本身两个因数，那么这个数就是质数。
注意，\(1\) 既不是质数，也不是合数！
2. 判定单个方法
首先，最暴力的做法肯定是从 \(1\) 枚举到 \(n\)。
bool isprime(int x) {if (i <= 1) return false;for (int i = 2; i < x; i++) {if (x % i == 0) return false;}return true;
}
这个时间复杂度是 \(O(x)\) 的。
但我们注意到，如果 \(i\) 可以被 \(x\) 整除，那么 \(\dfrac{x}{i}\) 也可以被 \(x\) 整除，所以枚举到 \(\sqrt{x}\) 即可。
bool isprime(int x) {if (x <= 1) return false;for (int i = 2; i * i <= x; i++) {if (x % i == 0) return false; }return true;
}
3. 分解质因数
如果 \(a\) 能被 \(b\) 整除，那么 \(b\) 就是 \(a\) 的因数。
根据唯一分解定理
任何一个大于 \(1\) 的整数都可以被分解成有限个质数的乘积的形式。
所以可以写成
所以，可以枚举质数来分解质因数。
vector<int> getfactor(int x) {vector<int> res;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {res.push_back(i);while (n % i == 0) n /= i;}}if (x != 1) res.push_back(x);return res;
}
有什么问题吗？
注意到，\(i \times i\) 可能爆 \(int\)！！！
因数的数量
完全平方数有奇数个因数，非完全平方数有偶数个因数。
\(n\) 最多有多少个因数？
答：\(2\sqrt n\) 个。
实际上，\(1\) 到 \(n\) 的因数个数之和的数量级只有 \(n\log n\)，所以单个数的因数个数期望是 \(\log\)。
但实际差常数倍。
筛法
埃氏筛，原理是利用倍数关系找出合数。
bitset<N> vis;vector<int> init_prime() {vector<int> prime;for (int i = 2; i <= N; i++) {if (!vis[i]) {prime.push_back(i);for (int j = i * i; j <= N; j += i) {vis[j] = yrue;}}} return prime;
}
二、最大公因数
前言：
借鉴了亿下 OI-WIKI。
定义
最大公约数即为 Greatest Common Divisor，常缩写为 gcd．
一组整数的最大公约数，是指所有公约数里面最大的一个．
欧几里得算法
如果我们已知两个数 \(a\) 和 \(b\)，如何求出二者的最大公约数呢？
不妨设 \(a > b\)．
我们发现如果 \(b\) 是 \(a\) 的约数，那么 \(b\) 就是二者的最大公约数．
我们通过证明可以得到 \(\gcd(a,b)=\gcd(b,a \bmod b)\)。
在部分 GCC 中可以用 __gcd(a, b) 函数来求最大公约数，使用该函数可能会导致预期之外的问题（用 long long）。
如果两个数 \(a\) 和 \(b\) 满足 \(\gcd(a, b) = 1\)，我们称 \(a\) 和 \(b\) 互质．
三、同余
如果两个数 \(a\)，\(b\)模 \(m\) 得到的结果相同，那么我们就称 \(a\) 和 \(b\) 在模 \(m\) 的意义下同余。
比如 \(12\) 和 \(15\) 就在模 \(3\) 的意义下同余。
在模 \(m\) 意义下同余的两个数，做模 \(m\) 意义下的 \(+\)、\(-\)、\(\times\) 时可以相互替换，结果不变
比如 \((12 + 1) \mod 3 = 1\)，\((15 + 1) \mod 3 = 1\)。
但是除法不行！
除法要求逆元。
逆元就是解 \(ax \equiv 1 \pmod{P}\) 这个方程。
所以 \(x \equiv a^{-1} \pmod P\)。
所以可以用 exgcd，可以用 Quickpow。