高精度乘法,是指计算超过标准数据类型能够表达的计算范围的乘法计算。
如果计算机结果已经超过long long所能表示的范围,将会得到溢出后的答案(结果不正确,也不能计算)
这时候就需要用到高精度乘法算法,所谓高精度乘法算法,就是通过录入字符数组的形式保存数字为字符串,然后逐一取出录入的数字字符,转换成对应的int数字进行计算,然后利用计算机善于重复循环处理数据的特点,模拟乘法竖式的计算过程,通过进位和错位相加的形式,得到高精度计算结果。
#include<stdio.h>
#include<string.h>
int main()
{
int c[100000]={0};
int k=0,carry=0,x=1,i;
char a[100000],b[100000];
gets(a);
gets(b);
int a_length=strlen(a),b_length=strlen(b);
//乘法竖式的方法👇
for( i=a_length-1;i>=0;i--)
{
for(int j=b_length-1;j>=0;j--)
{
c[k]=(a[i]-'0')*(b[j]-'0')+carry+c[k];
carry=c[k]/10;//carry 进位
c[k]%=10;
k++;
}
c[k]+=carry;//可能最高位有进位
carry=0;//被乘数的第k+1个数开始,carry清0
k=x;//————错位相加
x++;
}
for( i=10000-1;i>0;i--)
if(c[i]) break;//去掉前导0
for(int j=i;j>=0;j--)
printf("%d",c[j]);//逆序输出
return 0;
}
最后是刘汝佳高精度结构体
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
struct BigInteger {
static const int BASE = 100000000;
static const int WIDTH = 8;
vector<int> s;
BigInteger(long long num = 0) { *this = num; } // 构造函数
BigInteger operator = (long long num) { // 赋值运算符
s.clear();
do {
s.push_back(num % BASE);
num /= BASE;
} while(num > 0);
return *this;
}
BigInteger operator = (const string& str) { // 赋值运算符
s.clear();
int x, len = (str.length() - 1) / WIDTH + 1;
for(int i = 0; i < len; i++) {
int end = str.length() - i*WIDTH;
int start = max(0, end - WIDTH);
sscanf(str.substr(start, end-start).c_str(), "%d", &x);
s.push_back(x);
}
return *this;
}
BigInteger operator + (const BigInteger& b) const {
BigInteger c;
c.s.clear();
for(int i = 0, g = 0; ; i++) {
if(g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = g;
if(i < s.size()) x += s[i];
if(i < b.s.size()) x += b.s[i];
c.s.push_back(x % BASE);
g = x / BASE;
}
return c;
}
};
ostream& operator << (ostream &out, const BigInteger& x) {
out << x.s.back();
for(int i = x.s.size()-2; i >= 0; i--) {
char buf[20];
sprintf(buf, "%08d", x.s[i]);
for(int j = 0; j < strlen(buf); j++) out << buf[j];
}
return out;
}
istream& operator >> (istream &in, BigInteger& x) {
string s;
if(!(in >> s)) return in;
x = s;
return in;
}
#include<set>
#include<map>
set<BigInteger> s;
map<BigInteger, int> m;
int main() {
BigInteger y;
BigInteger x = y;
BigInteger z = 123;
BigInteger a, b;
cin >> a >> b;
cout << a + b << "\n";
// cout << BigInteger::BASE << "\n";1
return 0;
}