国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁(yè) > 編程 > C++ > 正文

C++實(shí)現(xiàn)大整數(shù)乘法

2020-01-26 13:24:45
字體:
來(lái)源:轉(zhuǎn)載
供稿:網(wǎng)友

算法競(jìng)賽入門經(jīng)典 這本書并沒有對(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í)有所幫助,也希望大家多多支持武林網(wǎng)。

發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 瓮安县| 闽侯县| 榆中县| 晋城| 宾阳县| 延津县| 宜城市| 措美县| 永安市| 大宁县| 布拖县| 玉溪市| 盐山县| 准格尔旗| 桐柏县| 利辛县| 潜江市| 介休市| 本溪| 浮山县| 东阿县| 泾阳县| 犍为县| 闽清县| 应城市| 阳信县| 江永县| 美姑县| 红桥区| 安阳县| 华蓥市| 霍林郭勒市| 通化县| 马龙县| 长宁区| 武川县| 宣城市| 利川市| 佛山市| 东海县| 罗甸县|