#gj004. 高精度除以低精度

高精度除以低精度

高精度除以低精度

题目描述

​ 给定一个大整数 A(其位数可能超过普通整数类型的表示范围)和一个正整数 B(B 在 long long 范围内),请使用高精度除以低精度(Big Integer Division by Small Integer) 计算 A ÷ B 的商和余数,并分别输出。

算法概念

​ 高精度除以低精度是指用一个大整数(位数很多)除以一个可以用基本整数类型(如 long long)表示的整数。该方法模拟手工竖式除法的过程,从被除数最高位开始,逐位计算商和余数,时间复杂度为 O(n),其中 n 为被除数的位数。

算法原理与步骤

  1. 字符串读入:将大整数 A 以字符串形式读入,方便处理任意长度的数字。将除数 B 读入为 long long 类型。
  2. 正序存储:将字符串中的数字字符转换为整数,按原顺序(从高位到低位)存入整型数组 a1 中。
  3. 模拟竖式除法:初始化余数 x = 0。从最高位到最低位遍历被除数的每一位:
    • 更新当前被除数:x = x * 10 + a1[i]
    • 计算商的一位:c1[i] = x / B
    • 更新余数:x = x % B
  4. 去除前导零:商的数组中可能存在高位的 0(例如 123 / 100 = 1,商为 001,需去除前导 0)。从最高位开始找到第一个非零数字的位置 k,若商全为 0,则 k 保留最低位(即 k = la - 1)。
  5. 输出结果:第一行输出商(从 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。