C++實(shí)現(xiàn)大整數(shù)乘法
算法競(jìng)賽入門(mén)經(jīng)典 這本書(shū)并沒(méi)有對(duì)大數(shù)乘法實(shí)現(xiàn),所以自己補(bǔ)充了一下,乘法的實(shí)現(xiàn)很簡(jiǎn)單,就是再其數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上把每寬為8位的十進(jìn)制數(shù)看成多項(xiàng)式的系數(shù),vector的下標(biāo)看成多項(xiàng)式的指數(shù),然后再對(duì)應(yīng)相乘相加就可以了,注意系數(shù)超過(guò)8位 將超八位的補(bǔ)分進(jìn)位。
我這里是笛卡爾相乘。一般來(lái)說(shuō)是夠用的。
但其實(shí)多項(xiàng)式乘法算法還有很多更高效的。
#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;
}
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
MinGW-w64 C/C++編譯器下載和安裝的方法步驟(入門(mén)教程)
如果電腦沒(méi)有安裝MinGW-w64 C/C++編譯器,就無(wú)法運(yùn)行g(shù)cc命令,本文主要介紹了MinGW-w64 C/C++編譯器下載和安裝的方法步驟,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-02-02
Qt編寫(xiě)地圖遷徙圖的實(shí)現(xiàn)示例
本文主要介紹了Qt編寫(xiě)地圖遷徙圖的實(shí)現(xiàn)示例,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12
C語(yǔ)言使用ffmpeg實(shí)現(xiàn)單線程異步的視頻播放器
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言如何使用ffmpeg實(shí)現(xiàn)單線程異步的視頻播放器功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以嘗試一下2022-12-12
C++實(shí)現(xiàn)LeetCode(85.最大矩形)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(85.最大矩形),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語(yǔ)言實(shí)現(xiàn)紅黑樹(shù)的實(shí)例代碼
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)紅黑樹(shù)的實(shí)例代碼,有需要的朋友可以參考一下2013-12-12
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單推箱子小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)推箱子小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-11-11
簡(jiǎn)單掌握C++編程中的while與do-while循環(huán)語(yǔ)句使用
這篇文章主要介紹了C++編程中的while與do-while循環(huán)語(yǔ)句使用,區(qū)別就是while是先判斷再執(zhí)行,而do-while是先執(zhí)行再判斷,需要的朋友可以參考下2016-01-01
QT中QColorDialog開(kāi)發(fā)實(shí)例
QColorDialog是Qt框架中用于選擇顏色的對(duì)話框類,本文主要介紹了QT中QColorDialog開(kāi)發(fā)實(shí)例,具有一定的參考價(jià)值,感興趣的可以了解一下2023-11-11

