[ C++ 快速高精度模板 ] [ BigN类 ] 大整数类 高精度 模板 BigInt FFT 快速傅里叶变换
2024-08-30 06:45:08
【原创 转载请注明】瞎写的，如果代码有错，或者各位大佬有什么意见建议，望不吝赐教
更新日志：
对于规模较小的整数乘法使用$$O(n^2)$$方法，提高速度
modify()和operator[]的bug修正
除法速度提升
修正了除法崩溃的问题
修正了除数为零崩溃的问题
/**
* BigN Beata v1.3.1
* By: Nathaniel
* 13th,Dec,2017
**/ //This file provides four operation for big-intgers
//You can use class 'BigN' to define a variable.
//Follow operators are available
//+ - * / % = += -= *= /= %= > < >= <= == !=
//these operators can used between BigN and BigN or BigN and int. //You can use function print() to print a BigN to stdout.
//printn() will print a '\n' at the end.
//Function getstr() and str() will return a std::string-type string. //IN SAFE MODE, you can access k-th digit, from 0-th high digits, by [].
//Or you can also modify x-th digit by modify(x,y). //In this template, multipy operator is implicated by fast_Fourier_transform,
//Which can calculate convolution of to n-vectors in O(nlogn) time.
//When number is small, this code still use O(n^2) algorithm.
//and divide operator is implicated by dichotomy. //-O2 or -O3 optimize option is recomended. //**********************************************************************//
//If you delete the follow definition,the calc speed will improve
//but when number become huge, especially over 2000000 digits,
//it may NOT work correctly.
//So, to make sure that you answer is correct, do NOT delete this line. //#define SAFE_CALC_MODE //**********************************************************************// #include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <vector>
#include <complex> const double _pi=acos(-); class _fast_Fourier_transform
{
typedef std::complex<double> Cmplx;
typedef std::vector<Cmplx> E;
typedef std::vector<int> Vec;
private:
int _n,_m,_N;
Vec R; //butterfly operation
inline void Expand(int temp)
{
int L=; for(_N=;_N<=temp;_N<<=,L++);
R.resize(_N+);
for(int i=;i<_N;++i) R[i]=R[i>>]>>|(i&)<<(L-);
return ;
} //Fast Fourier Transform
void FFT(E& A,int f)
{
for(int i=;i<_N;++i) if(i<R[i]) swap(A[i],A[R[i]]);
for(int i=;i<_N;i<<=)
{
Cmplx wn(cos(_pi/i),f*sin(_pi/i));
for(int j=;j<_N;j+=i<<)
{
Cmplx w(,);
for(int k=;k<i;++k,w*=wn)
{
Cmplx x=A[j+k],y=w*A[i+j+k];
A[j+k]=x+y; A[i+j+k]=x-y;
}
}
} return ;
} inline Vec Mul(E& A,E& B)
{
Expand(_n+_m); A.resize(_N+); B.resize(_N+);
FFT(A,); FFT(B,);//DFT
for(int i=;i<=_N;++i) A[i]*=B[i];//MUL
FFT(A,-);//IDFT
std::vector<int> vec;
for(int i=;i<_n+_m-;++i)
vec.push_back((int)(A[i].real()/_N+0.5));
//fix deviation
return vec;
} public:
inline Vec multi(Vec& AA,Vec& BB)
{
E A,B;
_n=AA.size(); _m=BB.size();
//turn two vectors to complex
A.resize(_n); B.resize(_m);
for(int i=;i<_n;++i) A[i]=AA[i];
for(int i=;i<_m;++i) B[i]=BB[i];
return Mul(A,B);
}
}; class _normal_mul
{
//O(n^2) multiply
typedef std::vector<int> Vec;
private:
inline Vec mul(Vec& A,Vec& B)
{
Vec vec; int _n,_m;
_n=(int)A.size(),_m=(int)B.size();
vec.resize(_n+_m);
for(int i=;i<_n;++i) for(int j=;j<_m;++j)
vec[i+j]+=A[i]*B[j];
return vec;
}
public:
inline Vec multi(Vec& AA,Vec& BB) { return mul(AA,BB); }
}; #ifndef SAFE_CALC_MODE
#define DIGITS 1000
#else
#define DIGITS 10
#endif class Divide_By_Zero_Error { }; class _data_container_of_BigN
{
private:
bool sym;//0 positive,1 negetive
unsigned int length;//total length of the number
std::vector<int> vec;//vector of data public:
typedef _data_container_of_BigN _this_class;
inline void _set_zero()
{ sym=; length=; vec.clear(); vec.push_back(); }
_data_container_of_BigN() { _set_zero();}
_data_container_of_BigN(int x)
{
//turn int to BigN
_set_zero();
if(x) vec.pop_back();
if(x<) sym=true,x=-x;
while(x)
{
vec.push_back(x%DIGITS);
x/=DIGITS;
}
update_length();
}
_data_container_of_BigN(const char* str)
{
int _n=strlen(str),data=,base=,t=;
vec.clear(); if(str[]=='-') sym=true,t=;
for(int i=_n-; i>=t; --i)
{
data=data+(str[i]-)*base;
#ifndef SAFE_CALC_MODE
if((_n-i)%==)
#endif
{
vec.push_back(data),data=,base=;
continue;
}
base*=;
}
vec.push_back(data);
update_length();
} inline _this_class operator=(const char* str)
{
//turn char* to BigN
int _n=strlen(str),data=,base=,t=;
vec.clear(); if(str[]=='-') sym=true,t=;
for(int i=_n-; i>=t; --i)
{
data=data+(str[i]-)*base;
#ifndef SAFE_CALC_MODE
if((_n-i)%==)
#endif
{
vec.push_back(data),data=,base=;
continue;
}
base*=;
}
vec.push_back(data);
update_length();
return *this;
} inline _this_class operator =(int x)
{
//turn int to BigN
_set_zero();
if(x) vec.pop_back();
if(x<) sym=true,x=-x;
while(x)
{
vec.push_back(x%DIGITS);
x/=DIGITS;
}
update_length();
return *this;
} inline _this_class operator -()
{
_this_class C=*this;
C.sym=!C.sym;
return C;
} inline int& operator[](int x) { return vec[x]; } inline bool is_positive() { return !sym; }
inline bool is_negetive() { return sym; } //Fix -0 to 0
inline void fix_zero()
{ if(sym && length== && vec[]==) sym=!sym; } //get k-th digit
inline int getkth(const int x)
{
if(x>=(int)length) return -;
return vec[length-x-];
}
//Modify
inline bool modify(const int x,const int y)
{
if(x>=(int)length) return false;
vec[length-x-]=y; update_length(); return true;
} inline _this_class operator+(_this_class& B)
{
if(!sym && !B.sym) return positive_add(B);
if(sym && B.sym) return -positive_add(B);
if(sym && !B.sym)
{
if(compare_abs(B)>) return -positive_minus(B);
return B.positive_minus(*this);
}
if(compare_abs(B)>) return positive_minus(B);
return -B.positive_minus(*this);
} inline _this_class operator-(_this_class& B)
{
if(!sym && !B.sym)
{
if(compare_abs(B)>) return positive_minus(B);
return -B.positive_minus(*this);
}
if(sym && B.sym)
{
if(compare_abs(B)>) return -positive_minus(B);
return B.positive_minus(*this);
}
if(!sym && B.sym) return positive_add(B);
return -B.positive_add(*this);
} inline _this_class operator*(_this_class& B)
{
return sym^B.sym?-positive_muliply(B):
positive_muliply(B);
} inline _this_class operator/(_this_class& B)
{
try
{
return sym^B.sym?-positive_divide(B):
positive_divide(B);
}catch(...)
{
std::cerr << std::endl;
std::cerr << "\tError: Division is 0." << std::endl;
}
return B;
} inline _this_class operator%(_this_class& B)
{
try
{
return sym^B.sym?-positive_mod(B):
positive_mod(B);
}catch(...)
{
std::cerr << std::endl;
std::cerr << "\tError: Division is 0." << std::endl;
}
return *this;
} inline _this_class operator+(int B){ _this_class t=B; return *this+t; }
inline _this_class operator-(int B){ _this_class t=B; return *this-t; }
inline _this_class operator*(int B){ _this_class t=B; return *this*t; }
inline _this_class operator/(int B){ _this_class t=B; return *this/t; }
inline _this_class operator%(int B){ _this_class t=B; return *this%t; } inline _this_class operator+=(_this_class& B) { return *this=*this+B; }
inline _this_class operator-=(_this_class& B) { return *this=*this-B; }
inline _this_class operator*=(_this_class& B) { return *this=*this*B; }
inline _this_class operator/=(_this_class& B) { return *this=*this/B; }
inline _this_class operator%=(_this_class& B) { return *this=*this%B; }
inline _this_class operator+=(int B) { return *this=*this+B; }
inline _this_class operator-=(int B) { return *this=*this-B; }
inline _this_class operator*=(int B) { return *this=*this*B; }
inline _this_class operator/=(int B) { return *this=*this/B; }
inline _this_class operator%=(int B) { return *this=*this%B; } //Print func will print the number to stdout in casual format
void print()
{
if(is_negetive()) printf("-");
#ifdef SAFE_CALC_MODE
for(int i=vec.size()-;i>=;--i)
printf("%d",vec[i]);
#else
printf("%d",vec[vec.size()-]);
for(int i=vec.size()-;i>=;--i)
printf("%03d",vec[i]);
#endif
return ;
}
//Print func will print the number to 'str' in casual format
void print_to_str(std::string& str)
{
str="";
char tempstr[];
if(is_negetive()) str="-";
#ifdef SAFE_CALC_MODE
for(int i=vec.size()-;i>=;--i)
sprintf(tempstr,"%d",vec[i]),
str+=tempstr;
#else
sprintf(tempstr,"%d",vec[vec.size()-]);
str+=tempstr;
for(int i=vec.size()-;i>=;--i)
sprintf(tempstr,"%03d",vec[i]),
str+=tempstr;
#endif
return ;
} inline unsigned int size() { return vec.size(); } /*
* this func
* returns 1 if *this>B
* returns -1 if *this<B
* return 0 if *this==B
*/
inline int compare_abs(_this_class& B)
{
if(length>B.length) return ;
if(length<B.length) return -;
for(int i=vec.size()-;i>=;--i)
if(vec[i]>B[i])return ;
else if(vec[i]<B[i]) return -;
return ;
} protected: inline void clear_zero()
//This func deletes leading zero
{
while(!vec[vec.size()-] && vec.size()!=)
vec.pop_back();
return ;
} /***************************************************************/
//CALL THIS FUNCTION AFTER EVERY OPERATION TO MAKE ANSWER CORRECT
#ifndef SAFE_CALC_MODE
inline void update_length()
//fixup length and leading zero
{
clear_zero();
if(vec.size()== && vec[]==) length=;
else if(vec[vec.size()-]/)length=vec.size()*;
else if(vec[vec.size()-]/)length=vec.size()*-;
else length=vec.size()*-;
return ;
}
#else
//fixup length and leading zero
inline void update_length()
{
clear_zero();
length=vec.size(); return ;
}
#endif
/***************************************************************/ //carry the vec
//notice: call update_length() after calling this func
inline void Go_up()
{
int t=vec.size();
for(int i=;i<t-;++i)
{
vec[i+]+=vec[i]/DIGITS;
vec[i]%=DIGITS;
}
while(vec[t-]>=DIGITS)
vec.push_back(vec[t-]/DIGITS),vec[t-]%=DIGITS,t++;
return ;
} //resize the vector
inline void resize(int x) { vec.resize(x); } inline int get_quotient(_this_class& R,_this_class& B,
_this_class* Map)
//This func get a quotient for divide operator by dichotomy
{
if(R.compare_abs(B)<) return ;
int l=,r=DIGITS,mid;
while(l<r-)
{
mid=l+((r-l)>>);
if(mid && Map[mid].size()== && Map[mid][]==)
Map[mid]=B*mid;
int t=R.compare_abs(Map[mid]);
if(t>)l=mid;
else if(t<)r=mid;
else { l=mid; break; }
}
if(mid && Map[l].size()== && Map[l][]==) Map[l]=B*l;
R=R-Map[l];
return l;
} private: inline _this_class positive_add(_this_class& B)
//This func returns Abs(*this)+Abs(B)
//calling this func must garantee '*this' and 'B' are both positive
{
_this_class C;//ans
bool _Longer_vec; if(vec.size()>B.size()) _Longer_vec=;
else _Longer_vec=; //if B is shorter
if(_Longer_vec)
{
C.resize(vec.size()+);
//add shorter digits first
for(int i=;i<(int)B.size();++i)
{
C[i+]=(C[i]+vec[i]+B[i])/DIGITS;
C[i]=(C[i]+vec[i]+B[i])%DIGITS;
}//each saves 3 digits //calc rest digits
for(int i=B.size();i<(int)vec.size();++i)
{
C[i+]=(C[i]+vec[i])/DIGITS;
C[i]=(C[i]+vec[i])%DIGITS;
}
}
//if B is longer
else
{
C.resize(B.size()+);
//add shorter digits first
for(int i=;i<(int)vec.size();++i)
{
C[i+]=(C[i]+vec[i]+B[i])/DIGITS;
C[i]=(C[i]+vec[i]+B[i])%DIGITS;
}//each saves 3 digits //calc rest digits
for(int i=vec.size();i<(int)B.size();++i)
{
C[i+]=(C[i]+B[i])/DIGITS;
C[i]=(C[i]+B[i])%DIGITS;
}
}
C.update_length();
return C;
} inline _this_class positive_minus(_this_class& B)
//This func returns Abs(*this)-Abs(B)
//calling this func must garantee '*this > B'
{
_this_class C;//ans
C.resize(vec.size());
//calc first B.size() digits
for(int i=;i<(int)B.size();++i)
{
if(vec[i]+C[i]<B[i])C[i]+=DIGITS+vec[i]-B[i],C[i+]--;
else C[i]+=vec[i]-B[i];
}
//copy the rest digits
for(int i=B.size();i<(int)vec.size();++i)
C[i]+=vec[i];
C.update_length();
return C;
} inline _this_class positive_muliply(_this_class& B)
//This func returns Abs(*this)*Abs(B)
{
_this_class C=*this; double temp=log(vec.size()+B.size())/log(); if((vec.size()+B.size())*temp<vec.size()*B.size())
//Using fast Fourier transform if (n+m)log(n+m)<n*m
//to speed mul operation when data become huge
{
_fast_Fourier_transform F;
C.vec=F.multi(C.vec,B.vec);
}
else
//Using normal O(n*m) algorithm when n,m is small
{
_normal_mul F;
if(vec.size()<B.size())C.vec=F.multi(C.vec,B.vec);
else C.vec=F.multi(B.vec,C.vec);
} C.Go_up();
C.update_length();
return C;
} inline _this_class positive_divide(_this_class& B)
//This func returns Abs(*this)/Abs(B)
{
if(B.length== && B.vec[]==) throw Divide_By_Zero_Error();
_this_class C;
_this_class r;//Remainder _this_class Map[DIGITS+];
//save B*x to save time. //if dividend is less return 0
if(compare_abs(B)<) return C; //if dividend is equal to divisor return 1
if(compare_abs(B)==) { C[]=; return C; } C.resize(vec.size());
r.resize(B.size());
for(int i=B.size()-;i>=;--i)
r[i]=vec[vec.size()-B.size()++i];
r.update_length(); for(int i=vec.size()-B.size();i>=;--i)
{
r*=DIGITS; r[]+=vec[i]; r.update_length();
//dichotomy
int t=get_quotient(r,B,Map);
C[i]=t;
}
C.update_length();
return C;
} inline _this_class positive_mod(_this_class& B)
//This func returns Abs(*this)%Abs(B)
{
if(B.length== && B.vec[]==) throw Divide_By_Zero_Error();
_this_class r;//Remainder _this_class Map[DIGITS+];
//save B*x to save time. //if dividend is less return vec
if(compare_abs(B)<) return *this; //if dividend is equal to divisor return 1
if(compare_abs(B)==) return r; r.resize(B.size());
for(int i=B.size()-;i>=;--i)
r[i]=vec[vec.size()-B.size()++i];
r.update_length(); for(int i=vec.size()-B.size();i>=;--i)
{
r*=DIGITS; r[]+=vec[i]; r.update_length();
//dichotomy
get_quotient(r,B,Map);
}
return r;
}
}; //Use This Class in your program.
class BigN
{
public:
#ifdef SAFE_CALC_MODE
//You may NOT modify the digits directly.
//if number has NO x-th number, function will return -1
inline int operator[](const int x) { return _data.getkth(x); }
//This Func change x-th digit to y.(start from 0th,high digit)
//Returns false for failure, true for success.
inline bool modify(const int x,const int y)
{ return _data.modify(x,y); }
#endif //Fix -0 to 0
inline void Fix_zero() { _data.fix_zero(); } inline BigN operator = (const int B)
{ _data=B; Fix_zero(); return *this;}
inline BigN operator = (const char* B)
{ _data=B; Fix_zero(); return *this;} inline BigN operator + (BigN B)
{ B._data=_data+B._data; B.Fix_zero(); return B; }
inline BigN operator - (BigN B)
{ B._data=_data-B._data; B.Fix_zero(); return B; }
inline BigN operator * (BigN B)
{ B._data=_data*B._data; B.Fix_zero(); return B; }
inline BigN operator / (BigN B)
{ B._data=_data/B._data; B.Fix_zero(); return B; }
inline BigN operator % (BigN B)
{ B._data=_data%B._data; B.Fix_zero(); return B; }
inline BigN operator + (int B)
{ BigN C=B; C._data=_data+C._data; C.Fix_zero(); return C; }
inline BigN operator - (int B)
{ BigN C=B; C._data=_data-C._data; C.Fix_zero(); return C; }
inline BigN operator * (int B)
{ BigN C=B; C._data=_data*C._data; C.Fix_zero(); return C; }
inline BigN operator / (int B)
{ BigN C=B; C._data=_data/C._data; C.Fix_zero(); return C; }
inline BigN operator % (int B)
{ BigN C=B; C._data=_data%C._data; C.Fix_zero(); return C; }
inline BigN operator+=(BigN B)
{ _data+=B._data; Fix_zero(); return *this; }
inline BigN operator-=(BigN B)
{ _data-=B._data; Fix_zero(); return *this; }
inline BigN operator*=(BigN B)
{ _data*=B._data; Fix_zero(); return *this; }
inline BigN operator/=(BigN B)
{ _data/=B._data; Fix_zero(); return *this; }
inline BigN operator%=(BigN B)
{ _data%=B._data; Fix_zero(); return *this; }
inline BigN operator+=(int B)
{ _data+=B; Fix_zero(); return *this; }
inline BigN operator-=(int B)
{ _data-=B; Fix_zero(); return *this; }
inline BigN operator*=(int B)
{ _data*=B; Fix_zero(); return *this; }
inline BigN operator/=(int B)
{ _data/=B; Fix_zero(); return *this; }
inline BigN operator%=(int B)
{ _data%=B; Fix_zero(); return *this; } inline bool operator < (BigN B)
{
if(_data.is_positive() && B._data.is_positive())
return _data.compare_abs(B._data)<;
if(_data.is_negetive() && B._data.is_negetive())
return _data.compare_abs(B._data)>;
if(_data.is_positive() && B._data.is_negetive()) return false;
return true;
}
inline bool operator > (BigN B)
{
if(_data.is_positive() && B._data.is_positive())
return _data.compare_abs(B._data)>;
if(_data.is_negetive() && B._data.is_negetive())
return _data.compare_abs(B._data)<;
if(_data.is_positive() && B._data.is_negetive()) return true;
return false;
}
inline bool operator == (BigN B)
{
if(_data.is_positive()!=B._data.is_positive()) return ;
else return _data.compare_abs(B._data)==;
}
inline bool operator <= (BigN B) { return *this<B || *this==B; }
inline bool operator >= (BigN B) { return *this>B || *this==B; }
inline bool operator != (BigN B) { return !(*this==B); } inline bool operator < (int B) { return *this<(BigN)B; }
inline bool operator > (int B) { return *this>(BigN)B; }
inline bool operator <= (int B) { return *this<=(BigN)B; }
inline bool operator >= (int B) { return *this>=(BigN)B; }
inline bool operator != (int B) { return *this!=(BigN)B; }
inline bool operator == (int B) { return *this==(BigN)B; } inline void print() { _data.print(); }
inline void printn() { _data.print(); printf("\n"); } //These two functions both return std::string-type of the number.
//If it is the first time you try to get the string after an operation,
//you should use getstr(), for function str() will return the old
//string.
//Each time you call getstr(), the string will up-to-date.
//And you can use str(), after calling getstr() to save time.
inline std::string getstr(){ _data.print_to_str(_Str); return _Str; }
inline std::string str() { return _Str; } protected:
std::string _Str;
inline void refresh_str() { _data.print_to_str(_Str); } private:
//this class contains real data and does the exact calculation
typedef _data_container_of_BigN _data_class;
_data_class _data;
public:
BigN() {}
BigN(const int x) { _data=x; }
BigN(const char* x) { _data=x; }
}; BigN operator + (int A,BigN B) { return B+A; }
BigN operator * (int A,BigN B) { return B*A; } /***************************************************************************/ char a[],b[]; int main()
{
scanf("%s%s",a,b);
BigN x=a,y=b,T;
printf("a+b="); (x+y).printn();
printf("a-b="); (x-y).printn();
printf("a*b="); (x*y).printn();
printf("a/b="); (x/y).printn();
printf("a%%b="); (x%y).printn();
printf("a*1000+b="); (T=x*+y).printn();
printf("2nd digit=%c\n",T.getstr().c_str()[]); //These operation need definition of SAFE_CALC_MODE in line 33 //T.modify(3,9);
//printf("after modify 3rd digit to 9="); T.printn();
//printf("3rd digit=");printf("%d\n",T[3]);
//printf("after unavailable operatorion="); T.modify(100,9);
//T.printn();
//printf("unavailable access="); printf("%d\n",T[100]); /*****************************************************/
// Input: //
// 123 45 //
// Output: //
// a+b=168 //
// a-b=78 //
// a*b=5535 //
// a/b=2 //
// a%b=33 //
// a*1000+b=123045 //
// 2nd digit=3 //
// after modify 3rd digit to 9=123945 //
// 3rd digit=9 //
// after unavailable operatorion=123945 //
// unavailable access=-1 //
/*****************************************************/
return ;
}
最新文章
- MongoVUE1.6.9破解启动提示System.ArgumentException: 字体“Courier New”不支持样式“Regular”
- php 教程列表
- Wix 安装部署教程(十四) -- 多语言安装包之用户许可协议
- java web(一) 使用sql标签库+tomcat+mysql手动创建一个jsp练习总结
- jQuery的常用事件
- MyEclipse安装lombok
- putty 中文乱码解决方法
- 【面试题002】java实现的单例模式，c++实现单例模式，实现禁止拷贝
- 构建高性能WEB站点笔记三
- DataTable类
- 2.词法结构-JavaScript权威指南笔记
- eclipse 项目引入第三方jar包 3种方法
- 海思uboot启动流程详细分析（一）
- MD5加密加盐
- kubernetes命令详情
- was系统的远程调试
- [hive] hive 安装、配置
- Application Request Route实现IIS Server Farms集群负载
- VC播放mp3的方法
- UML学生成绩管理系统需求分析