大数运算
发布时间:2020-12-14 03:37:08 所属栏目:大数据 来源:网络整理
导读:进过测试,没有bug ?。 const int maxn = 9999 ; // 每位储存4位const int dig = 4 ;class BigNum{ public : int a[7150] ; int len ; BigNum(){len = 1 ; memset(a,sizeof(a)) ;} BigNum(const int) ; BigNum(const char*) ; BigNum operator *(const BigNu
进过测试,没有bug ?。 const int maxn = 9999 ; // 每位储存4位 const int dig = 4 ; class BigNum{ public : int a[7150] ; int len ; BigNum(){len = 1 ; memset(a,sizeof(a)) ;} BigNum(const int) ; BigNum(const char*) ; BigNum operator *(const BigNum &) const ; BigNum operator +(const BigNum &) const ; BigNum operator ^(const int &) const ; BigNum operator /(const int &) const ; int operator %(const int &) const ; friend ostream& operator <<(ostream &out,const BigNum&T) ; }; BigNum::BigNum(const int T){ int t = T ; len = 0 ; memset(a,sizeof(a)) ; while(t > maxn){ a[len++] = t - t/(maxn+1)*(maxn+1) ; t = t/(maxn+1) ; } a[len++] = t ; } BigNum::BigNum(const char* s){ memset(a,sizeof(a)) ; int t,i,j,k,id = 0,l = strlen(s) ; len = l/dig ; if(l%dig) len++ ; for(i = l-1 ; i >= 0 ; i -= dig){ t = 0 ; k = max(0,i - dig + 1); for(j = k ; j <= i ; j++) t = t*10 + s[j] - '0' ; a[id++] = t ; } } ostream& operator <<(ostream &out,const BigNum&T){ printf("%d",T.a[T.len-1]) ; for(int i = T.len-2 ; i >= 0 ; i--) printf("%04d",T.a[i]) ; return out ; } BigNum BigNum::operator*(const BigNum &T) const{ BigNum s ; int i,up,t ; for(i = 0 ; i < len ; i++){ up = 0 ; for(j = 0 ; j < T.len ; j++){ t = a[i]*T.a[j] + s.a[i+j] + up ; if(t > maxn){ s.a[i+j] = t - t/(maxn+1)*(maxn+1) ; up = t/(maxn+1) ; } else{ up = 0 ; s.a[i+j] = t ; } } if(up != 0) s.a[i+j] = up ; } s.len = len + T.len ; while(s.a[s.len-1] == 0 && s.len>1) s.len-- ; return s ; } BigNum BigNum::operator + (const BigNum &T) const{ BigNum s ; s.len = max(len,T.len) ; for(int i = 0 ; i < s.len ; i++){ s.a[i] += a[i] + T.a[i] ; if(s.a[i] > maxn){ s.a[i+1]++ ; s.a[i] %= (maxn+1) ; } } if(s.a[s.len]!=0) s.len++ ; return s ; } BigNum BigNum::operator^(const int &T)const{ BigNum s(1) ; BigNum x = *this ; int y = T ; for( ; y ; y >>=1){ if(y&1) s = s * x ; x = x * x ; } return s ; } BigNum BigNum::operator/ (const int &T)const{ BigNum s ; int i,down = 0 ; for(i = len - 1 ; i >= 0 ; i--){ s.a[i] = (a[i] + down*(maxn+1)) / T ; down = a[i] + down*(maxn+1) - s.a[i]*T ; } s.len = len ; while(s.a[s.len-1]==0 && s.len > 1) s.len-- ; return s ; } int BigNum::operator% (const int &T) const{ int i,d = 0 ; for(i = len-1 ; i >= 0 ; i--){ d = d*(maxn+1) + a[i] ; d %= T ; } return d ; } 1.1版 class BigNum{ public : int a[7150] ; int len ; BigNum(){len = 1 ; memset(a,sizeof(a)) ;} BigNum(const int) ; BigNum(const char*) ; BigNum operator *(const BigNum &) const ; BigNum operator +(const BigNum &) const ; BigNum operator ^(const int &) const ; BigNum operator /(const int &) const ; int operator %(const int &) const ; bool operator > (const BigNum &) const ; bool operator >= (const BigNum &) const ; friend ostream& operator <<(ostream &out,d = 0 ; for(i = len-1 ; i >= 0 ; i--){ d = d*(maxn+1) + a[i] ; d %= T ; } return d ; } bool BigNum::operator> (const BigNum &T) const{ if(len > T.len) return 1 ; else if(len == T.len){ int i = len-1 ; while(i >= 0 && a[i] == T.a[i]) i-- ; if(i >= 0 && a[i] > T.a[i]) return 1 ; else return 0 ; } else return 0 ; } bool BigNum::operator>= (const BigNum &T) const{ if(len > T.len) return 1 ; else if(len == T.len){ int i = len-1 ; while(i >= 0 && a[i] == T.a[i]) i-- ; if(i >= 0 && a[i] < T.a[i]) return 0 ; else return 1 ; } else return 0 ; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- [bigdata-078] python3 logging 的示例 TimedRotatingFileH
- 是否有一个Delphi事件保证在应用程序终止时但在任何表单被销
- Perl中if [-e $file] 判断
- 函数 – 之间的差异 和:在Lua
- Perl Learning - 1 (Breif introduction, Scalar)
- java – 无法从Spring应用程序上下文创建ThreadPoolExecut
- perl – 如何在字符串而不是文件上使用Template Toolkit?
- 学习perl点滴(二)
- Delphi,Dll中使用ActiveX控件
- vb.net 教程 3-8 窗体编程 容器 2 TabControl 1