AcWing 794. 高精度除法
原题链接
简单
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// div 函数用于将一个大整数(表示为向量 A)除以一个整数 b,并返回商和余数。
vector<int> div(vector<int> &A, int b, int &r) //r是引用传进去的
{
vector<int> C; // 用于存储除法结果的向量
r = 0; // 初始化余数为 0
// 从向量 A 的最后一个元素开始,进行除法操作
for (int i = A.size() - 1; i >= 0; i--)
{
r = r * 10 + A[i]; // 将当前余数乘以 10 并加上当前位的值
C.push_back(r / b); // 将商存入向量 C
r %= b; // 更新余数
}
reverse(C.begin(), C.end()); // 反转向量 C 以恢复正确的顺序
/* 例子 A=151 b=11
反转 C 使其变为 [3, 1, 0],现在 C 存储了从高位到低位的商。
while(C.size() > 1 && C.back() == 0) C.pop_back();:去除尾部的零,但在这个例子中没有零需要去除。
*/
// 移除向量 C 中前导的零
while (C.size() > 1 && C.back() == 0)
C.pop_back(); // 移除尾部的零 只要size>1 最高位有0 就pop_back
return C; // 返回结果
}
int main()
{
string a; // 输入的大整数(以字符串形式表示)
int b; // 除数
cin >> a >> b; // 从标准输入读取大整数 a 和整数 b
vector<int> A; // 用于存储大整数的向量
//除法从高位开始计算
for (int i = a.size() - 1; i >= 0; i--)
A.push_back(a[i] - '0');
int r; // 存储余数
auto C = div(A, b, r); // 调用 div 函数进行除法操作,获得商和余数
// 输出商,从高位到低位
for (int i = C.size() - 1; i >= 0; i--)
printf("%d", C[i]);
cout << endl << r << endl; // 输出余数,并换行
return 0; // 程序结束
}