数论基础

数论是信息学竞赛中非常重要的领域，涉及很多基础算法和技巧，尤其是在处理大数、同余运算、质数分解等问题时。在竞赛中，数论的知识不仅对解题提供了强有力的支持，而且很多算法背后都有深刻的数学原理。

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}) $)，比传统的逐位相乘方法更快。

算法步骤：

1. 假设有两个大数 ( x ) 和 ( y )，将它们分为两部分： $( x = 10^m a + b )，( y = 10^m c + d )$。

2. 计算三个部分：

3. ( ac )

4. ( bd )
5. ( (a+b)(c+d) - ac - bd )
6. 最终结果为： ($ 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算法更高效。

算法步骤：

1. 将大数分成三部分，例如$ (x = 10^m a + b + c)，(y = 10^m p + q + r)$，
2. 计算五个乘积：$(a \cdot p)，(b \cdot q)，(c \cdot r)，(a \cdot q + b \cdot p)，和 (b \cdot r + c \cdot q)$。
3. 通过组合这些结果，得到最终乘积。

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})$)。

算法步骤：

1. 将大数表示为多项式。
2. 通过FFT将多项式转换为点值表示。
3. 在点值表示下，进行多项式的点值乘法。
4. 利用逆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通常足够使用。