浅析高精度计算——乘法
高精度计算——乘法：
当数据类型开到2的63次方（long long的取值范围：-2^63——2^63-1，大约是-9* 10^18——+9* 10^18-1）都无法装下庞大的数据量时，可以使用数组按位存储，模拟列式乘法来计算。
1.高精度乘高精度（两数相乘）
#include<stdio.h>
#include<string.h>
const int maxn = 1e4+7;
int main () {
char number1[maxn], number2[maxn];
scanf("%s%s", &number1, &number2);
int n = strlen(number1), m = strlen(number2);
int a[n], b[m];
//高精度乘法运算初始化
int i ,j;
//把字符数组中的数字字符 倒序 放入int数组中
//其中 a[0] 为个位，a[1] 为十位，以此类推
for (i = 0, j = n - 1; i < n; i++, j--) {
a[i] = number1[j] - '0';
}
for (i = 0, j = n - 1; i < n; i++, j--) {
b[i] = number2[j] - '0';
}
//上面代码相当于
// 1 2 3 -> number1
// * 5 6 7 -> number2
// ____________________
//
int c[maxn]; //用来存储乘法的中间过程量
memset(c, 0, sizeof(int)*maxn);
//（按照乘法列式）一位一位地运算
for (i = 0; i < n; i++) { //用来错开一个进制位
for (j = 0; j < m; j++) {
c[i+j] += a[i] * b[j];
}
}
//上面代码相当于
// 1 2 3 --> number1
// * 5 6 7 --> number2
// ____________________
// 7 14 21
// 6 12 18
// 5 10 15
//____________________________
// 5 16 34 32 21
//进位处理
for (i = 0; i < n + m; i++) {
if (c[i] >= 10) {
c[i+1] += c[i] / 10; //进位
c[i] %= 10;
}
}
//上面代码相当于
// 1 2 3 --> number1
// * 5 6 7 --> number2
// ____________________
// 7 14 21
// 6 12 18
// 5 10 15
//____________________________
// 6 9 7 4 1
//上面操作可以看成如下常规乘法列式计算
// 1 2 3 --> number1
// * 5 6 7 --> number2
// ____________________
// 8 6 1
// 7 3 8
// 6 1 5
//____________________________
// 6 9 7 4 1
for (j = maxn - 1; j > 0; j--) {
if (c[j] != 0) break;
}
for (i = j; i >= 0; i--) {
printf("%d", c[i]);
}
printf("\n");
return 0;
} 2.累乘情况（累乘到爆long long）
eg：NC16561国王的游戏————贪心+高精度累乘+配套高精度除法
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int l = 1;
int g[1000005];
struct person {
int l, r;
}a[100009];
bool cmp(person A, person B) {
return A.l * A.r < B.l* B.r;
//从小到大排序——贪心核心代码
//题目限制l、r<10000，所以两数相乘不爆int,此处不需要高精度乘法
}
void gj1(int x)//高精度乘法
{
for (int i = 1;i <= l;++i)g[i] *= a[x].l;//从低位开始乘
for (int i = 1;i <= l;i++)
{
g[i + 1] += (g[i] / 10);//对于每一位都除掉10得到的数字就是该向上进位的值
g[i] = g[i] % 10;//该元素本身保留余10的结果
}
l++;//数组长度要加一，即使最高一位没有进位，先加上也无妨，在之后也会把多加的长度去掉
while (g[l] > 9)//对于最高一位再向上进位，变成十进制
{
g[l + 1] += (g[l] / 10);
g[l] = g[l] % 10;
l++;
}
if (g[l] == 0)l--;//如果数组前面是0，则数组长度减一
}
void gj2() //配套高精度除法
{
for (int i = l;i >= 1;i--)//从高位开始
{
g[i - 1] += ((g[i] % a[n].r) * 10);//除不尽的小数部分（余数），向低位*10相加
g[i] /= a[n].r;//本身保留除后的整数部分
}
while (g[l] == 0)l--;//如果数组首位是0，数组长度减一，因为不用输出0
if (l == 0)//但是如果最终数组长度为0，又由于每个人都会得到赏金，所以每个人最多只能分到1赏金
cout << 1 << endl;
}
int main() {
cin >> n;
for (int i = 0;i <= n;i++)
cin >> a[i].l >> a[i].r;
sort(a + 1, a + n + 1, cmp);
g[1] = a[0].l;
for (int i = 1;i < n;i++)
gj1(i);
gj2();
for (int i = l;i >= 1;i--)
cout << g[i];
cout << '\n';
return 0;
}
