#gj004. 高精度除以低精度
高精度除以低精度
高精度除以低精度
题目描述
给定一个大整数 A(其位数可能超过普通整数类型的表示范围)和一个正整数 B(B 在 long long 范围内),请使用高精度除以低精度(Big Integer Division by Small Integer) 计算 A ÷ B 的商和余数,并分别输出。
算法概念
高精度除以低精度是指用一个大整数(位数很多)除以一个可以用基本整数类型(如 long long)表示的整数。该方法模拟手工竖式除法的过程,从被除数最高位开始,逐位计算商和余数,时间复杂度为 O(n),其中 n 为被除数的位数。
算法原理与步骤
- 字符串读入:将大整数 A 以字符串形式读入,方便处理任意长度的数字。将除数 B 读入为 long long 类型。
- 正序存储:将字符串中的数字字符转换为整数,按原顺序(从高位到低位)存入整型数组 a1 中。
- 模拟竖式除法:初始化余数 x = 0。从最高位到最低位遍历被除数的每一位:
- 更新当前被除数:x = x * 10 + a1[i]
- 计算商的一位:c1[i] = x / B
- 更新余数:x = x % B
- 去除前导零:商的数组中可能存在高位的 0(例如 123 / 100 = 1,商为 001,需去除前导 0)。从最高位开始找到第一个非零数字的位置 k,若商全为 0,则 k 保留最低位(即 k = la - 1)。
- 输出结果:第一行输出商(从 k 到 la-1 依次输出),第二行输出余数 x。
输入格式
第一行一个非负整数 A(可能很大,无前导零,除非 A 为 0)。 第二行一个正整数 B(B 在 long long 范围内)。
输出格式
第一行输出商(不含前导零,若商为 0 则输出 0)。
第二行输出余数(为一个非负整数)。
输入输出样例
输入输出样例 #1
123456789
123
123456789
123
输入输出样例 #2
100
3
33
1
输入输出样例 #3
0
5
0
0
数据规模与约定
- A 的长度不超过 500 位(即 1 ≤ |A| ≤ 500,A 可能为 0)。
- 1 ≤ B ≤ 10^18(B 在 long long 范围内,保证运算不溢出)。
- 时间限制:1 秒
- 内存限制:256 MB
提示
代码提示:
char a[505];
long long b;
cin >> a >> b;
int la = strlen(a);
int a1[505] = {}, c1[505] = {};
// 将 a 正序存入 a1(高位在前)
for (int i = 0; i < la; i++) {
// TODO: a1[i] = a[i] - '0';
}
long long x = 0; // 当前余数
// 逐位做除法
for (int i = 0; i < la; i++) {
// TODO: x = x * 10 + a1[i];
// TODO:
// TODO:
}
// 去除商的前导零
int k = 0;
while (c1[k] == 0 && k < la - 1) {
// TODO:
}
// 输出商
for (int i = k; i < la; i++) {
cout << c1[i];
}
cout << endl;
// 输出余数
cout << x << endl;
运用提示:
- 高精度除以低精度的核心是模拟竖式除法,从高位向低位逐步计算。每次将当前余数乘以 10 加上下一位数字,再除以除数得到商的一位。
- 注意余数 x 的数据类型必须足够大。
- 商的前导零需要去除,注意当商为 0 时(如 0 / 5),循环条件 k < la-1 保证保留最后一位 0。