题意
给定两个正整数,计算它们的商和余数。正整数长度的范围是1到100000。
PS:除数不为0.
分析
1.这里是高精度除以低精度,使用的除法运算是我们人类熟悉的。
2.从被除数的高位开始,每个数位都尝试去除以除数,一直到最低位。
3.最后倒序输出商。
代码
高精度除低精度
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
//a[]存储的是A,c[]存储的是A除以B的商
int a[N], c[N];
//cnt1是a[]的长度,cnt3是c[]的长度
int cnt1, cnt3;
//高精度除以低精度
//a[]是A,b是B,r是余数,注意r需要加上引用符
int div(int a[], int b, int &r) {
for (int i = cnt1; i >= 1; i--) {
//t是在之前高位运算得到的余数,来到当前数位需要乘以10
r = a[i] + r * 10;
c[i] = r / b;
r %= b;
}
int len = cnt1;//len的值等于cnt1
//去掉前导零
while (len > 1 && c[len] == 0) len--;
return len;
}
int main() {
string x;//x是高精度的大数
int y; //y是低精度的大数
cin >> x >> y;
//将被除数x倒序存到a[]中
for (int i = x.size() - 1; i >= 0; i--)
a[++cnt1] = x[i] - '0';
int r = 0;//r为余数
cnt3 = div(a, y, r);
//倒序输出c[],即除法运算结果的商
for (int i = cnt3; i >= 1; i--)
printf("%d", c[i]);
//输出除法运算结果的余数
printf("\n%d\n", r);
return 0;
}