【C++】PAT - Basic Level 1017 A除以B（大数除法）

本题要求计算 A/B，其中 A 是不超过 1000 位的正整数，B 是 1 位正整数。你需要输出商数 Q 和余数 R，使得 A=B×Q+R 成立。

输入格式：

输入在一行中依次给出 A 和 B，中间以 1 空格分隔。

输出格式：

在一行中依次输出 Q 和 R，中间以 1 空格分隔。

输入样例：

123456789050987654321 7

输出样例：

17636684150141093474 3

三. 题目分析

        本题是一道大数的除法题，因为被除数A 是不超过 1000 位的正整数，远远大于了int整型变量的取值范围（-2^31~2^31-1），甚至超过了long long数据类型的取值范围（-2^63~2^63-1，位数最多只有19位）。因此，仅仅使用这些数据类型来存储A是不行的。

        因此，需要使用字符串来记录A的数据，而且，可以借助中小学所学的竖式除法的思想，对字符串的每一位依次进行运算，并使用整型变量carry来记录当前所“退”的位数。

由于是10进制，所以在每一位当中：

当前位的计算结果 = (当前位的数字 + 上一位所“退”的位数 * 10) / 除数：

即ret = (A[i] + carry*10) / B；

计算完毕之后，将每位所得到的结果增添到字符串Q当中，再计算所要“退”到下一位的数carry：

当前位将要“退”到下一位的数 = (当前位的数字 + 上一位所“退”的位数 * 10) mod 除数：

即carry = (A[i] + carry*10) % B；

以此类推，再循环计算下一位的结果。当每一位都计算完毕之后，此时的carry值就是最后的余数R了。

四. 代码（C++）

#include
#include
#include
using namespace std;
int main()
{
	string A, Q;
	int B, R;

	cin >> A; cin >> B;
	int carry = 0;
	int ret = 0;
	int num1;

	for (int i = 0; i < A.size(); i++)
	{
		num1 = A[i] - '0';
		ret = (carry * 10 + num1) / B;
		Q.append(to_string(ret));
		carry = (carry * 10 + num1) % B;   //必须最后再更新carry值，不然ret会被影响
	}
	R = carry;

	if (Q[0] == '0'&& Q.size()>1)  //去掉字符串最前面的0.若商数只有一个数字0，则不去掉。
	{
		Q.erase(0,1);
	}
	cout << Q << " " << R << endl;
	system("pause");
	return 0;
}

五. 总结

        本题是一道入门级的大数计算题，所采用的方法借用了每位依次计算的竖式思想。实际上，许多大数计算题都可以采用这种方法来进行计算，用字符串存储数字，并使用变量来记录进位、退位的值，按每一位依次计算。

PS：有些题目（诸如加法、乘法）由于是从最后一位开始进行计算，因此要先对字符串进行逆序，而本题是除法，从第一位开始计算，因此就不需要逆序了。