高精度乘法（C++，高精度）

采用IPO思路实现：

（1）I：

为了实现个位对齐、方便计算，将数字当作字符串读入，然后转为数字；

（2）P：

大致思路如下

采用二层循环实现，每次循环的操作：

sum_next += (a * b + sum) / 10;

sum = (a * b + sum) % 10;

（3）O：

输出结果即可

代码如下：

/* 高精度乘法 */
#include <iostream>
using namespace std;
const int max_len = 4096;

int num[2][max_len] = { 0 };
int len[2] = { 0 };
int sum[max_len] = { 0 };

void in_put() {
	string str[2];
	cin >> str[0] >> str[1];
	len[0] = str[0].size(); len[1] = str[1].size();

	for (int i = 0; i < 2; i++) {
		int i_1 = max_len - 1, i_2 = len[i] - 1;
		while (i_2 != -1) {
			num[i][i_1] = str[i][i_2] - '0';
			i_1--, i_2--;
		}
		len[i] = i_1;//边界判断
	}
}

int calc() {
	for (int i = 0; i < 2; i++) {//*0特判
		if (len[i] == max_len - 2 && num[i][max_len - 1] == 0) {
			return max_len - 1;
		}
	}

	int i_1 = max_len - 1, i_2 = max_len - 1;
	while (i_1 > len[0]) {
		i_2 = max_len - 1;
		int bia = max_len - 1 - i_1;//偏移量
		while (i_2 > len[1]) {
			sum[i_2 - bia - 1] += (sum[i_2 - bia] + num[0][i_1] * num[1][i_2]) / 10;
			sum[i_2 - bia] = (sum[i_2 - bia] + num[0][i_1] * num[1][i_2]) % 10;
			i_2--;
		}
		i_1--;
	}
	int t = ++i_2 - (max_len - 1 - ++i_1) - 1;
	return sum[t] ? t : t + 1;//边界判断
}

void out_put(int high) {
	while (high != max_len) {
		cout << sum[high++];
	}
	cout << endl;
}

int main() {
	in_put();
	out_put(calc());
	return 0;
}

接下来说明一道例题

高精度求累加和

题目描述：

使用求和公式求1到N的累加（N最大可为100位的整数）

输入格式:

输入在一行中给出1个位数不超过100位的整数N。

输出格式:

对每一组输入，在一行中输出1+2+3+……+N的值。

输入样例:

10

输出样例:

55

解题思路：

看到题目可能会疑惑：累加和不是高精度加法吗？

然后看到题目描述就会明白，应该使用求和公式，所以实质上是高精度乘法

唯一需要注意的是就是sum / 2的操作了

while (i != max_len) {
	ans[i + 1] = (sum[i] % 2 ? 5 : 0);
	ans[i] += sum[i] / 2;
	i++;
}

思路形成了，接下来是代码的实现

只要将高精度乘法的输入部分稍微改动，然后再加上简单的除法处理就可以了

代码如下：

#include <iostream>
using namespace std;
const int max_len = 4096;

int num[2][max_len] = { 0 };
int len[2] = { 0 };
int sum[max_len] = { 0 };
int ans[max_len + 1] = { 0 };

void in_put() {
	string str;
	cin >> str;

	int i_1 = max_len - 1, i_2 = int(str.size()) - 1;
	while (i_2 != -1) {
		num[0][i_1] = num[1][i_1] = str[i_2] - '0';
		i_1--, i_2--;
	}
	len[0] = i_1;//边界判断

	i_1 = max_len - 1;
	num[1][i_1]++;
	while (num[1][i_1] / 10) {
		num[1][i_1 - 1] += num[1][i_1] / 10;
		i_1--;
	}
	len[1] = i_1 == len[0] ? len[0] - 1 : len[0];
}

int calc() {
	for (int i = 0; i < 2; i++) {//*0特判
		if (len[i] == max_len - 2 && num[i][max_len - 1] == 0) {
			return max_len - 1;
		}
	}

	int i_1 = max_len - 1, i_2 = max_len - 1;
	while (i_1 > len[0]) {
		i_2 = max_len - 1;
		int bia = max_len - 1 - i_1;//偏移量
		while (i_2 > len[1]) {
			sum[i_2 - bia - 1] += (sum[i_2 - bia] + num[0][i_1] * num[1][i_2]) / 10;
			sum[i_2 - bia] = (sum[i_2 - bia] + num[0][i_1] * num[1][i_2]) % 10;
			i_2--;
		}
		i_1--;
	}
	int t = ++i_2 - (max_len - 1 - ++i_1) - 1;
	return sum[t] ? t : t + 1;
}

int divi(const int high) {
	int i = high;
	while (i != max_len) {
		ans[i + 1] = (sum[i] % 2 ? 5 : 0);
		ans[i] += sum[i] / 2;
		i++;
	}
	return ans[high] ? high : high + 1;
}

void out_put(int high) {
	while (high != max_len) {
		cout << ans[high++];
	}
	cout << endl;
}

int main() {
	in_put();
	out_put(divi(calc()));
	return 0;
}

日志：

2022-10-28 发布

2023-1-10 改进思路和代码的实现