AcWing 794. 高精度除法
原题链接
简单
作者:
咲张熊猫人
,
2021-01-14 23:04:43
,
所有人可见
,
阅读 378
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
vector<int> div(vector<int>&A, int b, int &r)
{
r = 0; // 这里作为余数传出,初始化为0,防止传入时没有其初始化
vector<int> C;
for(int i = A.size() - 1; i >= 0; --i) // 注意与其他运算不同的是,除法的运算是从高位开始的
{
r = r * 10 + A[i]; //将当前余数乘以10 再加上 此时被除数当前要运算的位作为一个被除的位 乘以10再相加相当于除法的竖式运算中将数字拉下来的这个过程
C.push_back(r / b); // 将当前的余数 除以 除数, 得到的对应位的商 --》 push_back
r %= b; // 再将当前余数与除数取模得到新的余数
}
reverse(C.begin(), C.end()); //注意这个过程中是从高位开始的,故此时的vector的低位储存的是商的高位,这与其他三个运算不相同,故为了统一这里reverse处理
while(C.size() > 1 && C.back() == 0) C.pop_back(); //前导0处理
return C;
}
int main()
{
string s;
int b;
cin >> s >> b;
vector<int> A;
for(int i = s.size() - 1; i >= 0; --i)
A.push_back(s[i] - '0');
int r = 0;
auto C = div(A,b,r); //由于要求最后的输出有商还有余数,但返回值只有一个,故将商用vector返回,另一个用传出参数这里用引用实现
for(int i = C.size() - 1; i>=0; --i)
cout << C[i];
cout<<endl<<r<<endl;
}