高精度计算基础

1.2 高精度计算的应用场景

• 数论问题：
  • 大数阶乘计算
  • 大数幂运算
  • 组合数计算
• 密码学：
  • RSA算法
  • 大数素数测试
  • 离散对数问题
• 实际应用：
  • 金融计算
  • 科学计算
  • 精确计算

6.1 大数阶乘

问题描述：计算n的阶乘（n ≤ 1000）。

思路：使用高精度乘法，从1乘到n。

代码实现：

vector<int> factorial(int n) {
    vector<int> result = {1};  // 初始值为1
    
    for (int i = 2; i <= n; i++) {
        // 乘以当前数
        int carry = 0;
        for (int j = 0; j < result.size(); j++) {
            carry += result[j] * i;
            result[j] = carry % 10;
            carry /= 10;
        }
        
        // 处理剩余进位
        while (carry) {
            result.push_back(carry % 10);
            carry /= 10;
        }
    }
    
    return result;
}

6.2 大数加法

问题描述：计算斐波那契数列的第n项（n ≤ 10000）。

思路：使用高精度加法，逐项计算。

代码实现：

vector<int> fibonacci(int n) {
    if (n <= 1) return {n};
    
    vector<int> a = {0};  // f(0)
    vector<int> b = {1};  // f(1)
    
    for (int i = 2; i <= n; i++) {
        vector<int> c = add(a, b);  // f(i) = f(i-1) + f(i-2)
        a = b;
        b = c;
    }
    
    return b;
}

// 优化版本：原地修改
vector<int> fibonacci_optimized(int n) {
    if (n <= 1) return {n};
    
    vector<int> a = {0};  // f(0)
    vector<int> b = {1};  // f(1)
    
    for (int i = 2; i <= n; i++) {
        // 直接在b上进行修改
        int carry = 0;
        if (b.size() < a.size()) b.resize(a.size());
        
        for (int j = 0; j < a.size(); j++) {
            carry += a[j];
            if (j < b.size()) {
                carry += b[j];
                b[j] = carry % 10;
            } else {
                b.push_back(carry % 10);
            }
            carry /= 10;
        }
        
        while (carry) {
            b.push_back(carry % 10);
            carry /= 10;
        }
        
        // 交换a和b
        a.swap(b);
        b = move(a);
    }
    
    return b;
}

6.3 大数减法

问题描述：给定两个大数a和b，计算它们的差的绝对值。

思路：使用高精度减法，注意比较大小和处理借位。

代码实现：

vector<int> absolute_difference(string& a, string& b) {
    // 将字符串转换为数组
    vector<int> A = str2vec(a);
    vector<int> B = str2vec(b);
    
    // 确保A >= B
    if (!cmp(A, B)) swap(A, B);
    
    // 执行减法
    vector<int> result;
    int borrow = 0;
    
    for (int i = 0; i < A.size(); i++) {
        borrow = A[i] - borrow;
        if (i < B.size()) borrow -= B[i];
        result.push_back((borrow + 10) % 10);
        borrow = borrow < 0;
    }
    
    // 去除前导零
    while (result.size() > 1 && result.back() == 0)
        result.pop_back();
    
    return result;
}