P1480 A/B Problem

题目描述

输入两个整数 \(a,b\)，输出它们的商。

输入格式

两行，第一行是被除数，第二行是除数。

输出格式

一行，商的整数部分。

样例

输入

10
2

输出

5

提示

\(0\le a\le 10^{5000}\)，\(1\le b\le 10^9\)。

思路

通过题目数据范围可以发现是高精度除以单精度的题目。

假设被除数存储在整型数组 a 中，定义整型变量 x，x初始化为 0，每次执行“\(x=x \times 10+a \lbrack i \rbrack\)”并除以除数取整后，赋值到商的数组中，\(x\) 被余数更新。最后删去前导零。另外需要注意，除法运算是从高位到低位进行的，在字符串转为整型数组的过程中正序存储即可。处理前导零的时候也需要正向处理。

代码

#include <bits/stdc++.h>

using namespace std;

char str[50010];
long long a[50010], p, c[50010], len, r;

void read()
{
	scanf("%s%d", str, &p);
	len = strlen(str);
	for (int i = 0; i < len; i ++ )
		a[i + 1] = str[i] - '0';
}

void div()
{
	long long x = 0, fl = 0;
	for (int i = 1; i <= len; i ++ )
	{
		x = x * 10 + a[i];
		if (x / p)
			fl = 1;
		if (!fl)
			continue;
		c[++ r] = x / p;
		x %= p;
	}
}

void print()
{
	if (r == 0)
	{
		printf("0");
		return;
	}
	for (int i = 1; i <= r; i ++ )
		printf("%d", c[i]);
}

int main()
{
	read();
	div();
	print();
	return 0;
}

代码二：重载运算符

需要注意的是：由于 \(b\) 的最大值为 \(10^9\)，因此在模拟竖式除法执行“\(x=x \times 10+a \lbrack i \rbrack\)”的过程中，\(x\) 的最大值为“\((10^9-1) \times 10+9\)”，超出整型 \(\operatorname{int}\) 范围，所以 \(x\) 定义为 \(\operatorname{long long}\) 类型。

#include <bits/stdc++.h>

using namespace std;

char str[5010];

struct node
{
	int len, s[5010];
	node()
	{
		len = 0;
		memset(s, 0, sizeof(s));
	}
};

node operator / (const node &a, int b)
{
	node c;
	c.len = a.len;
	long long x = 0; // 注意 x 的范围
	for (int i = a.len; i >= 1; i -- )
	{
		x = x * 10 + a.s[i];
		c.s[i] = x / b;
		x %= b;
	}
	while (!c.s[c.len])
		c.len --;
	return c;
}

node read()
{
	node c;
	scanf("%s", str);
	if (str[0] == '0')
	{
		printf("0");
		exit(0);
	}
	int len = strlen(str);
	for (int i = 1; i <= len; i ++ )
		c.s[i] = str[len - i] - '0';
	c.len = len;
	return c;
}

void print(const node &a)
{
	for (int i = a.len; i >= 1; i -- )
		printf("%d", a.s[i]);
}

int main()
{
	node a, c;
	a = read();
	int p;
	scanf("%d", &p);
	c = a / p;
	print(c);
	return 0;
}