算法竞赛入门经典 这本书并没有对大数乘法实现,所以自己补充了一下,乘法的实现很简单,就是再其数据结构基础上把每宽为8位的十进制数看成多项式的系数,vector的下标看成多项式的指数,然后再对应相乘相加就可以了,注意系数超过8位 将超八位的补分进位。
我这里是笛卡尔相乘。一般来说是够用的。
但其实多项式乘法算法还有很多更高效的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
struct BigInteger{
static const int BASE = 100000000;
static const int WIDTH = 8;
vector< int > s;
BigInteger operator = ( const string& str){
s.clear();
int x, len=(str.length()-1)/WIDTH+1;
for ( int i=0;i<len;i++){
int r=str.length()-i*WIDTH;
int l=max(0,r-WIDTH);
sscanf (str.substr(l,r-l).c_str(), "%d" ,&x);
s.push_back(x);
}
return * this ;
}
BigInteger operator * ( const BigInteger& b){
BigInteger c;
int lena= this ->s.size(),lenb=b.s.size(),lenc=lena+lenb-1;
LL *buf = new LL[lenc+1];
for ( int i=0;i<lenc+1;i++)buf[i]=0;
for ( int i=0;i<lena;i++)
for ( int j=0;j<lenb;j++){
buf[i+j]+=( this ->s[i])*((LL)b.s[j]);
buf[i+j+1]+=buf[i+j]/BASE;
buf[i+j]=buf[i+j]%BASE;
}
for ( int i=0;i<lenc;i++)c.s.push_back(buf[i]);
if (buf[lenc])c.s.push_back(buf[lenc]);
return c;
}
BigInteger operator * ( const int & x){
char c[128];
sprintf (c, "%d" ,x);
string str(c);
BigInteger res;
res=str;
return * this *res;
}
};
ostream& operator<<(ostream& out, const BigInteger& b){
int len=b.s.size();
out<<b.s[len-1];
for ( int i=len-2;i>=0;i--){
int buf=b.s[i],h=8;
while (buf>0){buf/=10;h--;}
for ( int j=0;j<h;j++)out<<0;
if (b.s[i])out<<b.s[i];
}
return out;
}
int main()
{
int n;BigInteger b;
b= "1000000000000" ;
cout<< b<<endl;
cout<< (b*b)*4*b*b <<endl;
}
|
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/yinxiaobao97/article/details/83477734