数论是信息学竞赛中非常重要的领域，涉及很多基础算法和技巧，尤其是在处理大数、同余运算、质数分解等问题时。在竞赛中，数论的知识不仅对解题提供了强有力的支持，而且很多算法背后都有深刻的数学原理。
1. 素数与质因数分解¶
1.1 素数的基本概念¶
素数（Prime Number）：大于1的整数，且除了1和其本身外没有其他约数的数。例如，2、3、5、7、11、13等。
合数（Composite Number）：大于1且可以分解为多个素数相乘的整数。例如，4、6、8、9、10等。
质因数分解：将一个整数分解为若干个素数的乘积。每个数都有唯一的质因数分解。
1.2 素数判定¶
朴素算法：检查一个数是否能被从2到该数的平方根之间的数整除。时间复杂度为O(√n)。
埃拉托斯特尼筛法：用于筛选出一个区间内所有的素数，时间复杂度为O(n log log n)，适用于求大量素数。
米勒-拉宾素性测试：一种快速的素数判定方法，用于大数的素性测试，是基于概率的。
2. 最大公约数与最小公倍数¶
2.1 最大公约数（GCD）¶
欧几里得算法：通过递归（或迭代）来求解两个数的最大公约数，公式为：
$
GCD(a, b) = GCD(b, a\mod b)
$
直到 ( b = 0 )，此时 ( GCD(a, 0) = a )。
2.2 扩展欧几里得算法¶
扩展欧几里得算法：除了求最大公约数外，还能求出一对整数 ( x ) 和 ( y )，使得：
$
ax + by = GCD(a, b)
$
这个公式对于求解线性同余方程很有用。
2.3 最小公倍数（LCM）¶
- 通过最大公约数求最小公倍数，公式为：
$
LCM(a, b) = \frac{|a \times b|}{GCD(a, b)}
$
3. 模运算¶
3.1 模的基本性质¶
加法：$((a + b) \mod m = (a \mod m) + (b \mod m) \mod m)$
乘法：$((a \times b) \mod m = (a \mod m) \times (b \mod m) \mod m)$
减法：$((a - b) \mod m = (a \mod m) - (b \mod m) \mod m)$
3.2 模反元素¶
- 给定一个数 ( a ) 和模 ( m )，如果 ( a ) 和 ( m ) 互质（即 ( GCD(a, m) = 1 )），则存在一个整数 ( x )，使得：
$
a \times x \equiv 1 \pmod{m}
$
这个 ( x ) 就是 ( a ) 关于模 ( m ) 的乘法逆元。
求解方法：通过扩展欧几里得算法求解。
3.3 快速幂算法¶
-
计算大数的幂模。给定一个整数 ( a )，需要计算 ( a^b \mod m )。
快速幂：使用二分法（分治法）来加速幂的计算，时间复杂度为 O(log b)。 -
递归形式：
$
\text{fast_pow}(a, b, m) =
\begin{cases}
1 & \text{if } b = 0 \
a \times \text{fast_pow}(a, b-1, m) \mod m & \text{if } b \text{ is odd} \
(\text{fast_pow}(a, b/2, m))^2 \mod m & \text{if } b \text{ is even}
\end{cases}
$
4. 同余与同余方程¶
4.1 同余的定义¶
同余：两个整数 ( a ) 和 ( b ) 对模 ( m ) 同余，表示：
$
a \equiv b \pmod{m} \quad \text{if and only if} \quad m \mid (a - b)
$
其中 ( m ) 为模，表示“模 m 下的余数相同”。
4.2 线性同余方程¶
-
形式为：($ ax \equiv b \pmod{m} $)
求解步骤： -
使用扩展欧几里得算法求解最大公约数 ( GCD(a, m) )。
- 如果 ( GCD(a, m) ) 不整除 ( b )，则方程无解。
- 否则，可以通过求解 ( ax + my = GCD(a, m) ) 来得到解。
4.3 中国剩余定理¶
- 给定一组模线性方程：
$
\begin{cases}
x \equiv a_1 \pmod{m_1} \
x \equiv a_2 \pmod{m_2} \
\vdots \
x \equiv a_k \pmod{m_k}
\end{cases}
$
如果模数 ($ m_1, m_2, \dots, m_k $) 两两互质，则可以用中国剩余定理找到唯一解 ( x )（模 ($ m_1 m_2 \dots m_k $)）。
5. 费马小定理与欧拉定理¶
5.1 费马小定理¶
- 如果 ( p ) 是素数，且 ( a ) 不被 ( p ) 整除，则：
$
a^{p-1} \equiv 1 \pmod{p}
$
这个定理对于大数的幂模计算、素性测试等问题非常重要。
5.2 欧拉定理¶
- 对于任意整数 ( a ) 和 ( n )，如果 ( GCD(a, n) = 1 )，则：
$
a^{\phi(n)} \equiv 1 \pmod{n}
$
其中 ( $\phi(n) $) 是 ( n ) 的欧拉函数，表示小于 ( n ) 且与 ( n ) 互质的数的个数。
5.3 欧拉函数（φ函数）¶
欧拉函数 ( $\phi(n) $)：表示小于 ( n ) 的与 ( n ) 互质的数的个数。对于质数 ( p )，有 ($ \phi(p) = p - 1 $)；对于合数 ($ n = p_1^{k_1} \cdot p_2^{k_2} \cdot \dots \cdot p_r^{k_r} $)，有：
$
\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_r}\right)
$
6. 大数运算与快速算法¶
6.1 大数乘法¶
- 在处理超大整数时，可以使用分治法进行大数的快速乘法。
Karatsuba算法：通过分治法将大整数的乘法时间复杂度降低为 O(n^log3)。
6.2 快速模运算¶
- 当数字非常大时，直接计算 ($ a^b \mod m $) 是不可行的，使用 快速幂 和 分治法 可以高效计算。
大数乘法是指在处理超大整数时，传统的乘法算法（例如逐位相乘）会变得非常慢。因此，我们通常使用更高效的算法来进行大数乘法。以下是几种常见的大数乘法算法及其 C++ 实现：
1. 传统的逐位相乘算法¶
思路：¶
- 每位数相乘并将结果累加，处理结果中的进位。
- 这个算法的时间复杂度为 ($ O(n^2)$ )，其中 ( n ) 是数字的位数。
C++实现：¶
#include <iostream>
#include <vector>
using namespace std;
vector<int> multiplyBigNumbers(const vector<int>& num1, const vector<int>& num2) {
int n = num1.size();
int m = num2.size();
vector<int> result(n + m, 0); // 结果数组，大小为 n + m
// 从低位到高位进行相乘
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
int product = num1$i$ * num2$j$;
int sum = product + result$i + j + 1$;
result$i + j + 1$ = sum % 10; // 当前位
result$i + j$ += sum / 10; // 进位
}
}
// 移除前导零
while (result.size() > 1 && result$0$ == 0) {
result.erase(result.begin());
}
return result;
}
void printBigNumber(const vector<int>& num) {
for (int digit : num) {
cout << digit;
}
cout << endl;
}
int main() {
// 输入大数（按逆序存储）
vector<int> num1 = {3, 4, 2}; // 对应数字 243
vector<int> num2 = {8, 9, 1}; // 对应数字 198
// 计算大数乘法
vector<int> result = multiplyBigNumbers(num1, num2);
// 输出结果
printBigNumber(result); // 输出结果：48234
return 0;
}
解析：¶
num1和num2以逆序的方式存储，例如数字 243 存储为 {3, 4, 2}。multiplyBigNumbers函数通过逐位相乘并处理进位来计算大数的乘法。printBigNumber用于输出大数。
2. Karatsuba算法（分治法）¶
思路：¶
- Karatsuba算法是一种优化的大数乘法算法，通过将大数乘法问题分解为多个较小的子问题来减少计算复杂度。
- 该算法的时间复杂度为 ( $O(n^{\log_2 3}) \approx O(n^{1.585}) $)，比传统的逐位相乘方法更快。
算法步骤：¶
- 假设有两个大数 ( x ) 和 ( y )，将它们分为两部分： $( x = 10^m a + b )，( y = 10^m c + d )$。
- 计算三个部分：
- ( ac )
- ( bd )
- ( (a+b)(c+d) - ac - bd )
3. 最终结果为： ($ x \times y = 10^{2m} ac + 10^m ((a+b)(c+d) - ac - bd) + bd $)
C++实现：¶
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 对大数进行按位存储
vector<int> multiplyBigNumbersKaratsuba(const vector<int>& num1, const vector<int>& num2) {
int n = num1.size();
int m = num2.size();
int max_size = max(n, m);
if (max_size == 1) {
return {num1$0$ * num2$0$};
}
int mid = max_size / 2;
vector<int> num1_low(mid), num1_high(mid), num2_low(mid), num2_high(mid);
for (int i = 0; i < mid; i++) {
num1_low$i$ = num1$i$;
num2_low$i$ = num2$i$;
}
for (int i = mid; i < n; i++) {
num1_high$i - mid$ = num1$i$;
}
for (int i = mid; i < m; i++) {
num2_high$i - mid$ = num2$i$;
}
// 递归计算子问题
vector<int> ac = multiplyBigNumbersKaratsuba(num1_low, num2_low);
vector<int> bd = multiplyBigNumbersKaratsuba(num1_high, num2_high);
vector<int> ad_plus_bc = multiplyBigNumbersKaratsuba(num1_low, num2_high);
for (int i = 0; i < num1_high.size(); ++i) {
ad_plus_bc$i$ += multiplyBigNumbersKaratsuba(num1_high, num2_low);
}
// 合并结果
// 计算结果
// 10^(2*mid)*ac + 10^(mid)*(ad+bc) + bd
return result;
}
int main() {
// 示例使用的数字
vector<int> num1 = {3, 4, 2}; // 243
vector<int> num2 = {8, 9, 1}; // 198
printBigNumber(num1);
}
除了传统逐位相乘算法和Karatsuba算法，还有一些其他的高效大数乘法算法，包括 托宾-库尔布-斯图尔特算法（Toom-Cook） 和 快速傅里叶变换（FFT） 方法。这些方法可以在不同规模的大数乘法中提供不同的优势。下面将详细介绍这些算法及其实现。
3. 托宾-库尔布-斯图尔特算法（Toom-Cook算法）¶
思路：¶
Toom-Cook算法是一种分治法，它是Karatsuba算法的扩展。通过将大数分成更多的部分来进一步减少计算复杂度。一般的Toom-Cook算法会将数分成3部分，但也可以扩展为更多部分，从而进一步提高效率。
- Toom-Cook算法的时间复杂度通常为 ($O(n^{\log_3 5}$) \approx $O(n^{1.465})$)，比Karatsuba算法更高效。
算法步骤：¶
- 将大数分成三部分，例如$ (x = 10^m a + b + c)，(y = 10^m p + q + r)$，
- 计算五个乘积：$(a \cdot p)，(b \cdot q)，(c \cdot r)，(a \cdot q + b \cdot p)，和 (b \cdot r + c \cdot q)$。
- 通过组合这些结果，得到最终乘积。
C++实现：¶
由于Toom-Cook算法涉及到更多复杂的分治步骤以及更高的递归深度，代码实现较为复杂。下面是一个基本框架，你可以根据需要进一步实现。
#include <iostream>
#include <vector>
using namespace std;
vector<int> multiplyBigNumbersToomCook(const vector<int>& num1, const vector<int>& num2) {
// 基础部分：通过分治方法进行三分分解
int size1 = num1.size();
int size2 = num2.size();
// 分割数 num1 和 num2
int mid1 = size1 / 3;
int mid2 = size2 / 3;
vector<int> num1_low(num1.begin(), num1.begin() + mid1);
vector<int> num1_middle(num1.begin() + mid1, num1.begin() + 2 * mid1);
vector<int> num1_high(num1.begin() + 2 * mid1, num1.end());
vector<int> num2_low(num2.begin(), num2.begin() + mid2);
vector<int> num2_middle(num2.begin() + mid2, num2.begin() + 2 * mid2);
vector<int> num2_high(num2.begin() + 2 * mid2, num2.end());
// 递归地计算五个乘积
vector<int> a = multiplyBigNumbersToomCook(num1_low, num2_low);
vector<int> b = multiplyBigNumbersToomCook(num1_middle, num2_middle);
vector<int> c = multiplyBigNumbersToomCook(num1_high, num2_high);
// 组合最终的结果
// 需要补充细节处理和合并结果的逻辑
return a; // 这里简化了处理过程，实际上需要将不同的结果结合
}
int main() {
vector<int> num1 = {3, 4, 2}; // 对应数字 243
vector<int> num2 = {8, 9, 1}; // 对应数字 198
// 调用Toom-Cook乘法
vector<int> result = multiplyBigNumbersToomCook(num1, num2);
// 输出结果（简化版）
for (int digit : result) {
cout << digit;
}
cout << endl;
}
注意：¶
- Toom-Cook算法通过将大数分为三个部分来减少递归次数，适用于较大的数字。
- 这只是一个框架，实际代码中需要更加细致地处理结果的合并部分。
4. 快速傅里叶变换（FFT）¶
思路：¶
FFT是一种强大的数学工具，广泛应用于信号处理、图像处理等领域。它可以用来进行大数乘法，通过将大数的乘法转化为复数多项式的乘法。
FFT大数乘法的基本思路是：将大数视为多项式，利用FFT对这些多项式进行卷积运算，从而快速计算出它们的积。
- FFT的时间复杂度为 ($O(n \log n)$)，远远优于传统的 ($O(n^2)$) 和Karatsuba的 ($O(n^{\log_2 3})$)。
算法步骤：¶
- 将大数表示为多项式。
- 通过FFT将多项式转换为点值表示。
- 在点值表示下，进行多项式的点值乘法。
- 利用逆FFT将点值表示转换回常规表示，从而得到结果。
C++实现：¶
由于FFT涉及到复数运算和高效的算法实现，这里提供一个简化的思路框架，实际实现时需要用到复杂的FFT库或手动编写FFT算法。
#include <iostream>
#include <vector>
#include <cmath>
#include <complex>
using namespace std;
typedef complex<double> cd;
void fft(vector<cd>& a) {
int n = a.size();
if (n <= 1) return;
vector<cd> even(n / 2), odd(n / 2);
for (int i = 0; i < n / 2; ++i) {
even$i$ = a$2*i$;
odd$i$ = a$2*i + 1$;
}
fft(even);
fft(odd);
double angle = 2 * M_PI / n;
cd w(1), wn(cos(angle), sin(angle));
for (int i = 0; i < n / 2; ++i) {
a$i$ = even$i$ + w * odd$i$;
a$i + n / 2$ = even$i$ - w * odd$i$;
w *= wn;
}
}
void multiplyBigNumbersFFT(vector<int>& num1, vector<int>& num2) {
int n = 1;
while (n < max(num1.size(), num2.size())) n <<= 1;
n <<= 1; // Increase n to a power of 2
vector<cd> a(n), b(n);
for (int i = 0; i < num1.size(); ++i) {
a$i$ = cd(num1$i$, 0);
}
for (int i = 0; i < num2.size(); ++i) {
b$i$ = cd(num2$i$, 0);
}
fft(a);
fft(b);
for (int i = 0; i < n; ++i) {
a$i$ *= b$i$;
}
fft(a);
vector<int> result(n);
for (int i = 0; i < n; ++i) {
result$i$ = round(a$i$.real());
}
// 输出结果（处理进位等）
for (int digit : result) {
cout << digit << " ";
}
cout << endl;
}
int main() {
vector<int> num1 = {3, 4, 2}; // 243
vector<int> num2 = {8, 9, 1}; // 198
multiplyBigNumbersFFT(num1, num2);
return 0;
}
说明：¶
FFT的实现：这里的代码实现了FFT的基本框架，使用复数来表示和处理大数。通过FFT将大数转化为多项式的点值表示，进而进行快速计算。
结果处理：FFT的输出需要通过逆FFT转换回常规的大数表示，这涉及到如何处理浮动误差、进位等。
5. 总结¶
逐位相乘：简单易懂，但时间复杂度高，适用于小规模的数。
Karatsuba算法：通过分治法减少乘法次数，时间复杂度较低（$ (O(n^{\log_2 3})) $），适用于较大规模的数。
Toom-Cook算法：比Karatsuba更高效，通过进一步分治来减少计算量。
FFT大数乘法：效率非常高，适用于极大的数（时间复杂度 ($O(n \log n))$)，但是实现复杂，涉及复数和逆变换。
在实际应用中，根据数据规模和算法实现的复杂性，选择合适的大数乘法算法是非常重要的。对于大多数竞赛问题，Karatsuba算法和FFT通常足够使用。