#c

高精度计算进阶

高精度除法与取模运算

#c
@鞠大龙
魅客科创中心

CONTENTS

目录

1. 高精度计算回顾

1. 高精度计算回顾

  • 高精度计算基础：
    • 使用数组存储大数（个位在前）
    • 高精度加法：逐位相加并处理进位
    • 高精度减法：逐位相减并处理借位
    • 高精度乘法：大数与单精度数相乘
  • 进阶内容：
    • 高精度除法（大数除以小数）
    • 高精度取模运算
    • 高精度除法（大数除以大数）
    • 高精度数的快速幂
    • 高精度数的GCD
返回目录 信息学 高精度计算进阶 魅客科创中心

1. 高精度计算的应用场景

  • 密码学：
    • RSA算法中的大数除法和取模
    • 离散对数问题
    • 素数测试
  • 数论问题：
    • 大数的GCD计算
    • 模幂运算
    • 同余方程求解
  • 实际应用：
    • 精确除法计算
    • 大整数分解
    • 高精度小数计算
返回目录 信息学 高精度计算进阶 魅客科创中心

2. 高精度除法(大数除以小数)

2.1 高精度除法原理(大数除以小数)

基本思路：

  1. 将大数按位存储在数组中（个位在前）
  2. 从高位到低位逐位进行除法运算
  3. 处理余数
  4. 去除结果前导零

示例：计算 123 ÷ 4

步骤1：将数字存入数组
123 → [3,2,1]

步骤2：从高位到低位逐位除以4
  1 → 1 ÷ 4 = 0 余 1
  1*10 + 2 = 12 → 12 ÷ 4 = 3 余 0
  0*10 + 3 = 3 → 3 ÷ 4 = 0 余 3

结果：商 = 30，余数 = 3
返回目录 信息学 高精度计算进阶 魅客科创中心

2.2 高精度除法实现(大数除以小数)

核心代码：

// 高精度除以单精度，返回商和余数
pair<vector<int>, int> div(vector<int>& A, int b) {
    vector<int> C;
    int remainder = 0;
    
    // 从高位到低位处理
    for (int i = A.size() - 1; i >= 0; i--) {
        remainder = remainder * 10 + A[i];
        C.push_back(remainder / b);
        remainder %= b;
    }
    
    // 反转结果（因为是从高位开始处理的）
    reverse(C.begin(), C.end());
    
    // 去除前导零
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    
    return {C, remainder};
}

使用示例：

// 将大数转换为字符串
string bigNumberToString(vector<int>& num) {
    string result;
    for (int i = num.size() - 1; i >= 0; i--) {
        result += num[i] + '0';
    }
    return result;
}

// 示例：计算大数除以小数
void example() {
    string s = "123456789";
    vector<int> A;
    for (int i = s.length() - 1; i >= 0; i--) {
        A.push_back(s[i] - '0');
    }
    
    int b = 7;
    auto [quotient, remainder] = div(A, b);
    
    cout << s << " / " << b << " = " 
         << bigNumberToString(quotient) 
         << " 余 " << remainder << endl;
}
返回目录 信息学 高精度计算进阶 魅客科创中心

2.3 高精度除法优化(大数除以小数)

优化技巧：

  1. 预分配空间：
pair<vector<int>, int> div(vector<int>& A, int b) {
    vector<int> C;
    C.reserve(A.size());  // 预分配空间
    // ... 其余代码相同
}
  1. 特殊情况处理：
pair<vector<int>, int> div(vector<int>& A, int b) {
    if (b == 0) throw runtime_error("除数不能为0");
    if (b == 1) return {A, 0};
    
    vector<int> C;
    // ... 其余代码相同
}
  1. 位运算优化：
// 当b是2的幂时的优化
pair<vector<int>, int> div_power_of_two(vector<int>& A, int k) {
    vector<int> C;
    int mask = (1 << k) - 1;  // 用于取模
    int remainder = 0;
    
    for (int i = A.size() - 1; i >= 0; i--) {
        remainder = ((remainder * 10) + A[i]);
        C.push_back(remainder >> k);
        remainder &= mask;
    }
    
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    
    return {C, remainder};
}
返回目录 信息学 高精度计算进阶 魅客科创中心

3. 高精度取模运算

3.1 高精度取模原理

基本思路：

  1. 利用同余性质：(a + b) % m = ((a % m) + (b % m)) % m
  2. 从高位到低位逐位计算余数
  3. 每一步保持当前余数小于模数

示例：计算 123 % 7

步骤1：初始余数 r = 0
步骤2：从高位到低位处理
  r = (0 * 10 + 1) % 7 = 1
  r = (1 * 10 + 2) % 7 = 5
  r = (5 * 10 + 3) % 7 = 4

结果：123 % 7 = 4
返回目录 信息学 高精度计算进阶 魅客科创中心

3.2 高精度取模实现

核心代码：

// 高精度数对单精度数取模
int mod(vector<int>& A, int m) {
    int remainder = 0;
    
    // 从高位到低位处理
    for (int i = A.size() - 1; i >= 0; i--) {
        remainder = (remainder * 10 + A[i]) % m;
    }
    
    return remainder;
}

使用示例：

// 示例：计算大数对小数取模
void example() {
    string s = "123456789";
    vector<int> A;
    for (int i = s.length() - 1; i >= 0; i--) {
        A.push_back(s[i] - '0');
    }
    
    int m = 7;
    int remainder = mod(A, m);
    
    cout << s << " % " << m << " = " 
         << remainder << endl;
}
返回目录 信息学 高精度计算进阶 魅客科创中心

3.3 高精度取模优化

优化技巧：

  1. 预计算幂次：
// 预计算10^i % m，用于加速计算
vector<int> precompute_powers(int m, int max_length) {
    vector<int> powers(max_length);
    powers[0] = 1;
    for (int i = 1; i < max_length; i++) {
        powers[i] = (powers[i-1] * 10) % m;
    }
    return powers;
}

// 使用预计算的幂次加速取模
int mod_optimized(vector<int>& A, int m) {
    vector<int> powers = precompute_powers(m, A.size());
    int result = 0;
    
    for (int i = 0; i < A.size(); i++) {
        result = (result + A[i] * powers[i]) % m;
    }
    
    return result;
}
  1. Horner法则优化：
// 使用Horner法则优化取模运算
int mod_horner(vector<int>& A, int m) {
    int result = 0;
    for (int i = A.size() - 1; i >= 0; i--) {
        result = ((result * 10) % m + A[i]) % m;
    }
    return result;
}
返回目录 信息学 高精度计算进阶 魅客科创中心

4. 高精度除法(大数除以大数)

4.1 高精度除法原理(大数除以大数)

基本思路：

  1. 将大数按位存储在数组中（个位在前）
  2. 模拟手工除法的过程
  3. 通过试商和减法实现除法运算
  4. 去除结果前导零

示例：计算 123 ÷ 45

步骤1：将数字存入数组
123 → [3,2,1]
45 → [5,4]

步骤2：模拟手工除法
  12 ÷ 45 = 0 余 12
  123 ÷ 45 = 2 余 33

结果：商 = 2，余数 = 33
返回目录 信息学 高精度计算进阶 魅客科创中心

4.2 高精度除法实现(大数除以大数)

核心代码：

// 高精度除以高精度，返回商和余数
pair<vector<int>, vector<int>> div(
    vector<int>& A, vector<int>& B) {
    // 处理特殊情况
    if (B.size() == 1 && B[0] == 0) 
        throw runtime_error("除数不能为0");
    
    // 如果被除数小于除数，商为0，余数为被除数
    if (compare(A, B) < 0) 
        return {{0}, A};
    
    // 结果的位数最多为A的位数
    vector<int> quotient(A.size(), 0);
    vector<int> remainder = A;
    
    // 从高位开始处理
    int pos = A.size() - B.size();
    while (pos >= 0) {
        // 试商
        while (compare(remainder, 
               shift_left(B, pos)) >= 0) {
            quotient[pos]++;
            remainder = subtract(remainder, 
                       shift_left(B, pos));
        }
        pos--;
    }

    // 去除前导零
    while (quotient.size() > 1 && 
           quotient.back() == 0)
        quotient.pop_back();
    
    return {quotient, remainder};
}

// 比较两个大数的大小
int compare(vector<int>& A, vector<int>& B) {
    if (A.size() != B.size())
        return A.size() > B.size() ? 1 : -1;
    
    for (int i = A.size() - 1; i >= 0; i--) {
        if (A[i] != B[i])
            return A[i] > B[i] ? 1 : -1;
    }
    
    return 0;  // 相等
}

// 将大数左移pos位（相当于乘以10^pos）
vector<int> shift_left(vector<int>& A, int pos) {
    vector<int> result = A;
    result.insert(result.begin(), pos, 0);
    return result;
}
返回目录 信息学 高精度计算进阶 魅客科创中心

4.3 高精度除法优化(大数除以大数)

优化技巧：

  1. 二分试商：
// 使用二分法优化试商过程
int trial_quotient(vector<int>& A, vector<int>& B) {
    int left = 0, right = 9;
    while (left <= right) {
        int mid = (left + right) / 2;
        vector<int> product = multiply(B, mid);
        if (compare(product, A) <= 0 && 
            compare(multiply(B, mid + 1), A) > 0)
            return mid;
        else if (compare(product, A) > 0)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}
  1. 预处理除数：
// 预处理除数，使其最高位尽可能大
pair<vector<int>, int> normalize(vector<int>& A, vector<int>& B) {
    int scale = 10 / (B.back() + 1);
    vector<int> A_scaled = multiply(A, scale);
    vector<int> B_scaled = multiply(B, scale);
    return {B_scaled, scale};
}
  1. 使用更高效的减法：
// 优化减法操作，直接在原数组上进行修改
void subtract_in_place(vector<int>& A, vector<int>& B) {
    int borrow = 0;
    for (int i = 0; i < A.size(); i++) {
        int diff = A[i] - borrow;
        if (i < B.size()) diff -= B[i];
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        A[i] = diff;
    }
    
    // 去除前导零
    while (A.size() > 1 && A.back() == 0)
        A.pop_back();
}
返回目录 信息学 高精度计算进阶 魅客科创中心

5. 优化技巧

5. 优化技巧

  • 算法优化：
    • 使用二分试商
    • 预处理除数
    • 使用快速幂算法
    • 应用数学性质简化计算
  • 数据结构优化：
    • 使用更高效的存储方式
    • 考虑使用基数更大的表示法
    • 压缩存储减少内存使用
  • 代码优化：
    • 减少函数调用和内存分配
    • 使用位运算代替乘除
    • 循环展开和指令级并行
返回目录 信息学 高精度计算进阶 魅客科创中心

6. 经典例题

6.1 大数除法

问题描述：给定两个大整数a和b，计算a/b的商和余数。

思路：使用高精度除法，处理大数除以大数的情况。

代码实现：

pair<vector<int>, vector<int>> divide_large_numbers(string& a, string& b) {
    // 将字符串转换为数组
    vector<int> A, B;
    for (int i = a.length() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    for (int i = b.length() - 1; i >= 0; i--)
        B.push_back(b[i] - '0');
    
    // 处理特殊情况
    if (B.size() == 1 && B[0] == 0)
        throw runtime_error("除数不能为0");
    
    // 如果被除数小于除数，商为0，余数为被除数
    if (compare(A, B) < 0)
        return {{0}, A};
    
    // 计算商和余数
    return div(A, B);
}
返回目录 信息学 高精度计算进阶 魅客科创中心

6.2 模幂运算

问题描述：计算(a^b) % m，其中a、b和m都是大整数。

思路：使用快速幂算法和高精度取模运算。

代码实现：

// 计算(a^b) % m，其中a和m是大整数，b是小整数
vector<int> mod_pow(vector<int>& a, int b, vector<int>& m) {
    if (b == 0) return {1};  // a^0 = 1
    
    vector<int> result = {1};
    vector<int> base = a;
    
    while (b > 0) {
        if (b & 1) {  // 如果b的当前位为1
            result = mod_multiply(result, base, m);
        }
        base = mod_multiply(base, base, m);
        b >>= 1;
    }
    
    return result;
}

// 计算(a * b) % m
vector<int> mod_multiply(vector<int>& a, vector<int>& b, vector<int>& m) {
    vector<int> result = multiply(a, b);
    auto [_, remainder] = div(result, m);
    return remainder;
}
返回目录 信息学 高精度计算进阶 魅客科创中心

6.3 大数GCD

问题描述：计算两个大整数的最大公约数。

思路：使用辗转相除法和高精度除法。

代码实现：

// 计算两个大整数的最大公约数
vector<int> gcd(vector<int>& a, vector<int>& b) {
    // 确保a >= b
    if (compare(a, b) < 0)
        return gcd(b, a);
    
    // 如果b为0，则GCD为a
    if (b.size() == 1 && b[0] == 0)
        return a;
    
    // 辗转相除法
    auto [_, remainder] = div(a, b);
    return gcd(b, remainder);
}
返回目录 信息学 高精度计算进阶 魅客科创中心

7. 总结

7. 总结

核心要点：

  • 高精度除法和取模的基本思想
    • 模拟手工计算过程
    • 从高位到低位处理
    • 处理试商和余数
  • 实现技巧
    • 二分试商
    • 预处理除数
    • 快速幂优化
  • 常见错误
    • 试商不准确
    • 余数处理错误
    • 前导零处理不当

应用场景：

  • 密码学
    • RSA算法
    • 大数素性测试
    • 离散对数问题
  • 数论问题
    • 大数GCD
    • 模幂运算
    • 同余方程
  • 实际应用
    • 精确除法
    • 大整数分解
    • 高精度小数
返回目录 信息学 高精度计算进阶 魅客科创中心

8. 练习题目

8.1 初级练习题

  1. [POJ 1001] Exponentiation

    • 难度：★★☆☆☆
    • 描述：计算R^n，其中R是实数，n是整数
    • 思路：高精度乘法和小数点处理

  2. [HDU 1042] N!

    • 难度：★★☆☆☆
    • 描述：计算N的阶乘（N可达1000）
    • 思路：高精度乘法，注意优化

  3. [CSES 1713] Counting Divisors

    • 难度：★★☆☆☆
    • 描述：计算一个数的约数个数
    • 思路：高精度除法和取模
返回目录 信息学 高精度计算进阶 魅客科创中心

8.2 中级练习题

  1. [POJ 1503] Integer Inquiry

    • 难度：★★★☆☆
    • 描述：计算多个大整数的和
    • 思路：高精度加法，处理多个数

  2. [HDU 1576] A/B

    • 难度：★★★☆☆
    • 描述：计算(a/b) % 9973，其中a和b是大整数
    • 思路：高精度除法和取模，使用费马小定理

  3. [NOIP 2012] 分解质因数

    • 难度：★★★☆☆
    • 描述：将一个大整数分解为质因数的乘积
    • 思路：高精度除法和取模，素数筛选
返回目录 信息学 高精度计算进阶 魅客科创中心

8.3 高级练习题

  1. [POJ 2992] Divisors

    • 难度：★★★★☆
    • 描述：计算大数的所有约数
    • 思路：高精度除法和质因数分解

  2. [CSP-S 2019] 数列

    • 难度：★★★★☆
    • 描述：计算大数数列的通项公式
    • 思路：高精度除法和取模，数学归纳

  3. [USACO 2016 Dec Gold] Cow Checklist

    • 难度：★★★★☆
    • 描述：涉及大数计算的动态规划问题
    • 思路：高精度运算与DP结合
返回目录 信息学 高精度计算进阶 魅客科创中心

8.4 综合应用题

  1. [NOIP 2013] 找筷子

    • 难度：★★★★★
    • 描述：计算大数组合数，涉及高精度除法
    • 思路：高精度阶乘和除法

  2. [POJ 1845] Sumdiv

    • 难度：★★★★★
    • 描述：计算a^b的所有约数之和
    • 思路：高精度幂运算和数论知识

  3. [CSES 1712] Exponentiation II

    • 难度：★★★★★
    • 描述：计算a^(b^c) mod m
    • 思路：高精度模幂运算，欧拉定理
返回目录 信息学 高精度计算进阶 魅客科创中心
高精度计算进阶

#c

演讲者备注不会在演示模式中显示给观众，仅供演讲者参考。 每个关键页面都添加了备注，帮助演讲者更好地讲解内容。

封面页： - 欢迎学生，简要介绍本次课程的主题和目标 - 强调高精度计算进阶内容在算法竞赛中的重要性 - 本讲义将从基本概念到实际应用，系统讲解高精度计算的进阶算法

目录页： - 简要介绍讲义结构 - 高精度除法、取模运算、优化技巧、经典例题

转场页： - 回顾高精度计算的基本概念 - 引入高精度除法和取模运算

高精度计算回顾： - 基础知识回顾 - 与本讲义的关联

转场页： - 高精度除法(大数除以小数)的实现

转场页： - 高精度取模运算的实现

转场页： - 高精度除法(大数除以大数)的实现

转场页： - 高精度计算的优化方法

转场页： - 高精度计算的经典例题

转场页： - 总结高精度计算的核心思想和应用

转场页： - 高精度计算练习题目

练习题目部分结束，这些题目涵盖了高精度计算的各个难度和应用场景。 鼓励学生尝试解决这些问题，加深对高精度计算的理解。