大整数乘法 c++实现

#大整数乘法 c++实现| 来源: 网络整理| 查看: 265

算法竞赛入门经典这本书并没有对大数乘法实现，所以自己补充了一下，乘法的实现很简单，就是再其数据结构基础上把每宽为8位的十进制数看成多项式的系数，vector的下标看成多项式的指数，然后再对应相乘相加就可以了，注意系数超过8位将超八位的补分进位。

我这里是朴素模拟相乘。但是不是用的网上普遍的char表示1位数字(用1B去实现0~9实在有点浪费), 而是借用4B的int 实现0~10e8-1的存储,减少了不必要的复杂度

实际上这样优化朴素算法能通过很多需要FFT实现的OJ题.

#include #include #include #include using namespace std; typedef long long LL; struct BigInteger{ static const int BASE = 100000000; static const int WIDTH = 8; vector s; BigInteger operator = (const string& str){ s.clear(); int x, len=(str.length()-1)/WIDTH+1; for(int i=0;is.size(),lenb=b.s.size(),lenc=lena+lenb-1; LL *buf =new LL[lenc+1]; for(int i=0;i

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章