计蒜客 T1101：大整数的因子（高精度除法详解）

柔情只为你懂 2023-03-01 11:44 17阅读 0赞

**上一篇博客：[计蒜客 T1100：计算2的N次方（高精度乘法详解）][T1100_2_N]**

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。这篇博客来讲解一下高精度问题中的除法。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  高精度除法详解
 *   *  高精度算法简介
     *  大数的存储方式
     *  高精度除法实现
     *  高精度除法模板
     *  高精度除法完整模板
 *  T1101 大整数的因子详解
 *   *  题目信息
     *   *  题目描述
         *  输入格式
         *  输出格式
         *  样例输入
         *  样例输出
     *  题解
     *   *  解题思路
         *  解题代码

# 高精度除法详解 #

## 高精度算法简介 ##

高精度算法简介已经在之前的博客 [计蒜客T1098:大整数加法(高精度加法详解)][T1098] 中详细的介绍过了，这里就不再赘述了。

## 大数的存储方式 ##

大数的存储方式也在之前的博客 [计蒜客T1098:大整数加法(高精度加法详解)][T1098] 中详细的介绍过了，这里也不再赘述了。`但是我们要注意的是在除法的过程中我们是从最高位开始计算的，而不是像加减乘法一样从最低位开始计算，但是我们在除法的大整数存储中依旧是按照先存最低位再存高位。因为往往在一个高精度问题中不单单会涉及到除法，可能还会有加减乘法运算，所以为了方便我们在存储大整数的时候都是按照由低位到高位存储，即倒着存储`。下面来详细的介绍一下如何实现大整数除法。

## 高精度除法实现 ##

首先我们想一下我们在笔算除法的时候的计算步骤，在大整数 A1A2A3A4A5A6 ÷ b 先判断一下最高位的数字A1能不能除开 b，除不开就落下来然后再计算A1A2 是否能够除开 b；如果能够除开那么就将商写在上面然后求出余数 r ；再计算下一位,将余数 r \* 10 + A3，然后再计算商余数知道将所有的数位都除完，最后就剩下了最终的商和余数。

计算机中的大整数除法和我们笔算的时候思路是一样的，首先我们定义一个余数 r = 0，定义一个vector数组来存储商。先使 r = r \* 10 + A1，然后计算 r / b 的结果，并将其放到vector数组中，然后使 r %= b，求出当前的余数再进行下一位的运算即使 r = r \* 10 + A2，将 r / 10 的结果放到vector数组中，然后再计算余数 r %= b；一直循环往复下去直到算完所有的数位。

这里要注意还有一步操作就是讲vector数组进行翻转，因为我们在计算商的过程中是按照从最高位开始计算的，所以计算完成之后vector数组中的商是按照从高位到低位开始存储的，所以我们需要将其翻转过来使其从低位到高位存储方便我们 去除商中的前导零 和 进行下一次的加、减、乘运算。

去除前导零之后我们将结果数组返回即可，这里我们将余数 r 使用引用传递，所以最后只需要返回结果的vector数组即可。返回之后倒着输出即可。

## 高精度除法模板 ##

// 计算 A ÷ b = C ······ r
    vector<int> div(vector<int> &A, int b, int &r) { 
        vector<int> C;  // C数组用来存储商 
        r = 0;          // r 为余数
        int len_A = A.size();
        for (int i = len_A - 1; i >= 0; i--) { 
            r = r * 10 + A[i];
            C.push_back(r / b);
            r %= b;
        }
        // 将结果进行翻转，reverse()需要使用 <algorithm> 头文件
        reverse(C.begin(), C.end());
        // 去除前导零
        while (C.size() > 1 && C.back() == 0) C.pop_back();
        
        //返回结果数组
        return C;
    }

## 高精度除法完整模板 ##

**原题链接：[高精度除法][Link 1]**

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    // 计算 A ÷ b = C ······ r
    vector<int> div(vector<int> &A, int b, int &r) { 
        vector<int> C;  // C数组用来存储商 
        r = 0;          // r 为余数
        int len_A = A.size();
        for (int i = len_A - 1; i >= 0; i--) { 
            r = r * 10 + A[i];
            C.push_back(r / b);
            r %= b;
        }
        // 将结果进行翻转，reverse()需要使用 <algorithm> 头文件
        reverse(C.begin(), C.end());
        // 去除前导零
        while (C.size() > 1 && C.back() == 0) C.pop_back();
        
        //返回结果数组
        return C;
    }
    
    int main() { 
        string a;
        int b;
        
        cin >> a >> b;
        vector<int> A;
        // 将大整数 a 倒着存储到数组中
        for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
        
        int r;
        vector<int> ans = div(A, b, r);
        
        // 输出商 C 和余数 r
        int len = ans.size() - 1;
        for (int i = len; i >= 0; i--) printf("%d", ans[i]);
        cout << endl << r <<endl;
        return 0;
    }

# T1101 大整数的因子详解 #

## 题目信息 ##

**本题链接：[大整数的因子][Link 2]**

### 题目描述 ###

已知正整数 k 满足 2 ≤ k ≤ 9，现给出长度最大为 30 位的十进制非负整数 c，求所有能整除 c 的 k。

### 输入格式 ###

一个非负整数 c，c 的位数 ≤ 30。

### 输出格式 ###

若存在满足 c % k = 0 的 k，从小到大输出所有这样的 k，相邻两个数之间用单个空格隔开；若没有这样的 k，则输出"none"。

输出时每行末尾的多余空格，不影响答案正确性

### 样例输入 ###

> 30

### 样例输出 ###

> 2 3 5 6

## 题解 ##

### 解题思路 ###

由于题目只让我们输出大整数 c 在`2 <= i <= 9 范围内的因子`，所以我们只需要使用循环计算 c ÷ i 的余数 r 是否为 0 ，所以我们就不需要再计算商为多少，直接循环判断 r 是否为 0 即可。如果 r == 0 ，那么证明 此时的 i 是大数 c 的因子，那么就将其存储到 结果数组 ans 中，否则就不存储。

### 解题代码 ###

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    int div(vector<int> &A, int b) { 
        int r = 0;
        int len = A.size();
        for (int i = len - 1; i >= 0; i--) { 
            r = r * 10 + A[i];
            r %= b;
        }
        
        return r;
    }
     
    int main() { 
        string a;
        vector<int> A, ans;
        cin >> a;
        int len = a.size();
        for (int i = len - 1; i >= 0; i--) A.push_back(a[i] - '0');
        
        int r;
        for (int i = 2; i <= 9; i++) { 
            r = div(A, i);
            if (r == 0) { 
                ans.push_back(i);
            }
        }
        
        len = ans.size();
        if (len) { 
            for (int i = 0; i < len; i++) { 
                cout << ans[i] << " ";
            }
        } else { 
            cout << "none";
        }
        
        return 0;
    }

--------------------

> 我是ACfun，感谢大家的支持！  
> ![Tomcat我们走][Tomcat]

[T1100_2_N]: https://ac-fun.blog.csdn.net/article/details/107549771
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[T1098]: https://ac-fun.blog.csdn.net/article/details/107417161
[Link 1]: https://www.acwing.com/problem/content/796/
[Link 2]: https://nanti.jisuanke.com/t/T1101
[Tomcat]: /images/20230208/d5b69dd2442041b4a7095df980a19100.png