-
UID:136954
-
- 注册时间2012-10-05
- 最后登录2017-09-11
- 在线时间52小时
-
- 发帖41
- 搜Ta的帖子
- 精华0
- 金钱473
- 威望61
- 贡献值10
- 好评度53
-
访问TA的空间加好友用道具
|
大整数计算的代码: - #include"BigInt.h"
- BigInt::BigInt()
- {
- digital[0]=0;
- len=0; //当前大整数的长度
- sign=0; //符号为正
- isLegal=true;
- }
- BigInt::BigInt(qllong obj)
- {
- if(obj<0)
- {sign=true,obj = -obj;}
- else sign =false;
- digital[0]=obj%BASE;len=0;
- while(obj/=BASE)
- {digital[++len] = obj%BASE;}
- isLegal=true;
- }
- BigInt::BigInt(const BigInt &obj)
- {
- for(len=0,sign=obj.sign;len<=obj.len;len++)
- digital[len]=obj.digital[len];
- len--;
- isLegal=obj.isLegal;
- }
- BigInt& BigInt::operator =(const BigInt &obj)
- {
- for(len=0,sign=obj.sign;len<=obj.len;len++)
- digital[len]=obj.digital[len];
- len--;
- isLegal=obj.isLegal;
- return *this;
- }
- BigInt& BigInt::operator = (QString qstr)
- {
- int i=0,j,k;
- if(qstr[0]=='-')
- {sign=1;}
- else
- {
- sign=0;
- if(qstr[0]=='+')
- qstr.remove(0,1);
- }
- i=qstr.length();
- for(i=i-BASELEN,k=0;i>=sign;i-=BASELEN,++k)
- {
- for(j=0,digital[k]=0;j<BASELEN;++j)
- {
- if(qstr[i+j]==' ')continue;
- digital[k]=digital[k]*10+qstr[i+j].toAscii()-'0';
- }
- }
- i+=BASELEN;
- for(j=sign,digital[k]=0;j<i;++j)
- {
- if(qstr[j]==' ')continue;
- digital[k]=digital[k]*10+qstr[j].toAscii()-'0';
- }
- if(i==sign)k--;
- len=k;
- isLegal=true;
- return *this;
- }
- BigInt BigInt::operator +(const BigInt &obj)
- {
- BigInt sum;
- if(obj.sign==sign)
- { //同号加;
- int carry=0,i;
- for(i=0;i<=len && i <= obj.len;i++)
- {
- carry = carry +digital+obj.digital;
- sum.digital = carry%BASE;
- carry= carry/BASE;
- }
- for(;i<=len;i++)
- {carry = carry + digital, sum.digital = carry%BASE, carry/=BASE;}
- for(;i<=obj.len;i++)
- {carry = carry +obj.digital, sum.digital = carry%BASE,carry =carry/BASE;}
- if(carry&&i<MAXN){sum.digital=carry;sum.len=i;}
- else if(carry&&i==MAXN){isLegal=false;return *this;}
- else sum.len=i-1;
- sum.sign = sign;
- return sum;
- }
- else
- { //异号变同号减法;
- sum = obj;sum.sign= !sum.sign;
- return *this-sum;
- }
- }
- BigInt BigInt::operator +(int n)
- {
- if(n==0)
- return *this;
- if((sign==1&&n<0)||(sign==0&&n>0))
- {
- int temp,carry=0,i=0;
- if(n<0)n=-n;
- BigInt sum;
- if(len==0&&n>=BASE){digital[1]=0;}
- do
- {
- temp=n%BASE;n/=BASE;
- carry+=digital+temp;
- sum.digital=carry%BASE;
- carry= carry/BASE;
- i++;
- }while(n);
- while(i<=len)
- {
- carry+=digital;
- sum.digital=carry%BASE;
- carry=carry/BASE;
- i++;
- }
- if(carry&&i<MAXN){digital=carry,sum.len=i;}
- else if(carry&&i==MAXN){isLegal=false;return *this;}
- else sum.len=i-1;
- sum.sign=sign;
- return sum;
- }
- else
- {
- n=-n;
- return *this-n;
- }
- }
- BigInt BigInt::operator -(const BigInt &obj)
- {
- const BigInt *sub1,*sub2;
- BigInt quotient;
- if(sign==obj.sign)
- { //同号减;
- int i, carry=0;
- i = this->Cmp(obj,1); //绝对值比较;
- if(i==0)
- return quotient; //返回一个零
- else if(i<0)
- sub1=&obj,sub2=this,quotient.sign=!sign;
- else
- sub1=this,sub2 = &obj,quotient.sign=sign;
- for(i=0;i<=sub2->len;i++)
- {
- if((quotient.digital=sub1 ->digital-carry-sub2->digital)<0)
- carry = 1, quotient.digital+=BASE; //借位;
- else
- carry = 0;
- }
- for(;i<=sub1->len;i++)
- {
- if((quotient.digital = sub1->digital-carry )< 0 )
- carry = 1,quotient.digital +=BASE; //借位;
- else
- carry = 0;
- }
- do
- {
- --i;
- }while(i&"ient.digital==0);
- quotient.len = i;
- return quotient;
- }
- else
- { //异号变同号加:
- quotient = obj, quotient.sign =!obj.sign;
- return *this + quotient;
- }
- }
- BigInt BigInt::operator -(int n)
- {
- if(n==0)
- return *this;
- if((sign==1&&n<0)||(sign==0&&n>0))
- {
- BigInt quotient;
- qllong carry;
- int i;
- if(n<0)n=-n;
- quotient.sign=sign;
- if(len>1)
- {
- if((quotient.digital[0]=digital[0]-n%BASE)<0)
- carry=1,quotient.digital[0]+=BASE; //借位;
- else carry=0;
- i=1;
- if(n/=BASE)
- {
- if((quotient.digital[1]=digital[1]-n-carry)<0)
- carry=1,quotient.digital[1]+=BASE;
- else carry=0;
- i=2;
- }
- while(i<=len)
- {
- if((quotient.digital=digital-carry)<0)
- carry=1,quotient.digital+=BASE;
- else
- carry=0;
- i++;
- }
- if(quotient.digital[len]==0)
- quotient.len=len-1;
- else quotient.len=len;
- }
- else
- {
- carry=this->FirSecDigit()-n;
- if(carry<0){quotient.sign=true;carry=-carry;}
- quotient.digital[0]=carry%BASE;
- if(carry/=BASE)
- {quotient.digital[1]=carry;quotient.len=1;}
- }
- return quotient;
- }
- else
- {
- n=-n;
- return *this+n;
- }
- }
- BigInt BigInt::operator *(const BigInt &obj)
- {
- int i,j,maxlen;
- qllong carry;
- BigInt product;
- if(this->Zero()||obj.Zero())
- return product;
- maxlen=obj.len+len+1;
- if(maxlen>MAXN){isLegal=false;return *this;}
- memset(product.digital,0,sizeof(qllong)*maxlen );
- for(i = 0; i <= obj.len; i++)
- {
- for(j =0,carry=0;j<=len;j++)
- {
- carry += obj.digital * digital[j] +product.digital[j+i];
- product.digital[j+i] = carry%BASE;
- carry/=BASE;
- }
- if(carry&&i+j<MAXN)
- product.digital[i+j] = carry;
- }
- if(carry&&maxlen==MAXN)
- {isLegal=false;return *this;}
- if(!carry)maxlen--;
- product.len=maxlen;
- product.sign = sign^obj.sign;
- return product;
- }
- BigInt BigInt::operator *(int n)
- {
- int i,j,maxlen,temp;
- qllong carry;
- BigInt product;
- if(this->Zero()||n==0)return product;
- if(n>=BASE)maxlen=len+2;
- else maxlen=len+1;
- if(n<0){product.sign=!sign,n=-n;}
- else product.sign=sign;
- if(maxlen>MAXN){isLegal=false;return *this;}
- memset(product.digital,0,sizeof(qllong)*maxlen );
- temp=n%BASE;
- for(i=0,carry=0;i<=len;i++)
- {
- carry +=temp*digital;
- product.digital=carry%BASE;
- carry/=BASE;
- }
- if(carry&&i<MAXN) product.digital = carry;
- else if(carry&&i==MAXN){isLegal=false;return *this;}
- else product.digital=0;
- if(n/=BASE)
- {
- for(j=1,carry=0;j<=i;++j)
- {
- carry+=product.digital[j]+n*digital[j-1];
- product.digital[j]=carry%BASE;
- carry/=BASE;
- }
- if(carry&&j<MAXN) product.digital[j]=carry;
- else if(carry&&j==MAXN){isLegal=false;return *this;}
- else maxlen--;
- }
- if(n==0&&!carry)maxlen--;
- product.len=maxlen;
- return product;
- }
- BigInt BigInt::operator /(const BigInt &obj)
- {
- int k;
- qllong div;
- BigInt x,z,res;
- if(this->Zero())return *this;
- if(obj.sign==true||obj.Zero())
- {isLegal=false;return *this;}
- x = *this;
- x.sign=false;
- res.sign=obj.sign^sign;
- while( x.Cmp(obj,1) >0 )
- {
- k = x.len-obj.len;
- if( x.digital[x.len] > obj.digital[obj.len] )
- div =x.digital[x.len]/(obj.digital[obj.len]+1);
- else if(x.len>obj.len)
- {
- k--,
- div=(x.digital[x.len]*BASE+x.digital[x.len-1])/(obj.digital[obj.len]+1);
- }
- else break; //当x<=obj时跳出循环
- res+=(z=div).Shift(k);
- z*=obj;
- x-=z.Shift(k);
- }
- if(x.Cmp(obj,1)>=0)res=res+1;
- if(res.Zero())res.sign=false;
- else res.sign=sign;
- return res;
- }
- bool BigInt::operator >(const BigInt &obj)
- {
- int i;
- if(len>obj.len)
- return 1;
- if(len<obj.len)
- return 0;
- for(i=len;i>=0;--i)
- {
- if(digital>obj.digital)
- return 1;
- if(digital<obj.digital)
- return 0;
- }
- return 0;
- }
- bool BigInt::operator <(const BigInt &obj)
- {
- int i;
- if(len<obj.len)
- return 1;
- if(len>obj.len)
- return 0;
- for(i=len;i>=0;--i)
- {
- if(digital<obj.digital)
- return 1;
- if(digital>obj.digital)
- return 0;
- }
- return 0;
- }
- BigInt& BigInt::operator +=(const BigInt &obj)
- {
- if(obj.sign==sign)
- { //同号加;
- int carry=0,i;
- for(i=0;i<=len && i <= obj.len;i++)
- {
- carry = carry +digital+obj.digital;
- digital = carry%BASE;
- carry= carry/BASE;
- }
- for(;i<=len;i++)
- {carry = carry + digital,digital = carry%BASE, carry/=BASE;}
- for(;i<=obj.len;i++)
- {carry = carry +obj.digital,digital = carry%BASE,carry =carry/BASE;}
- if(carry&&i<MAXN)digital=carry;
- else if(carry&&i==MAXN){isLegal=false;return *this;}
- len=i-!carry;
- sign = sign;
- }
- else
- { //异号变同号减法;
- sign=!sign;
- BigInt temp=obj;
- *this=temp-*this;
- }
- return *this;
- }
- BigInt& BigInt::operator -=(const BigInt &obj)
- {
- const BigInt *sub1,*sub2;
- if(sign==obj.sign)
- { //同号减;
- int i, carry=0;
- i = this->Cmp(obj,1); //绝对值比较;
- if(i==0)
- {sign=false;digital[0]=0;len=0;return *this;}//返回一个零
- else if(i<0)
- sub1=&obj,sub2=this,sign=!sign;
- else
- sub1=this,sub2 = &obj;
- for(i=0;i<=sub2->len;i++)
- {
- if((digital=sub1 ->digital-carry-sub2->digital)<0)
- carry=1,digital+=BASE; //借位;
- else
- carry = 0;
- }
- for(;i<=sub1->len;i++)
- {
- if((digital = sub1->digital-carry )< 0 )
- carry = 1,digital +=BASE; //借位;
- else
- carry = 0;
- }
- do
- {
- --i;
- }while(i&&digital==0);
- len = i;
- }
- else
- { //异号变同号加:
- BigInt temp=obj;
- temp.sign =!obj.sign;
- *this=*this+temp;
- }
- return *this;
- }
- BigInt& BigInt::operator *=(const BigInt &obj)
- {
- int i,j,maxlen;
- qllong carry;
- BigInt product;
- if(this->Zero())
- {return *this;}
- if(obj.Zero())
- {*this=obj;return *this;}
- maxlen=obj.len+len+1;
- if(maxlen>MAXN){isLegal=false;return *this;}
- memset(product.digital,0,sizeof(qllong)*maxlen );
- for(i = 0; i <= obj.len; i++)
- {
- for(j =0,carry=0;j<=len;j++)
- {
- carry += obj.digital * digital[j] +product.digital[j+i];
- product.digital[j+i] = carry%BASE;
- carry/=BASE;
- }
- if(carry&&i+j<MAXN)
- product.digital[i+j] = carry;
- }
- if(carry&&maxlen==MAXN)
- {isLegal=false;return *this;}
- if(!carry)maxlen--;
- product.len=maxlen;
- product.sign = sign^obj.sign;
- *this=product;
- return *this;
- }
- BigInt BigInt::operator ^(int n)
- {
- BigInt temp=*this,res;
- if(n&1){res=temp;}
- else{res.digital[0]=1;}
- n>>=1;
- for(;n>0;n>>=1)
- {
- temp*=temp;
- if(n&1)
- {res*=temp;}
- if(temp.isLegal==false||res.isLegal==false)
- {this->isLegal=false;return *this;}
- //判断数据溢出,已在*=中完成判断。
- }
- return res;
- }
- BigInt BigInt::operator %(BigInt obj)
- {
- int k;
- qllong div;
- BigInt x;
- if(this->Zero())return *this;
- if(obj.Zero()){isLegal=false;return *this;}
- x = *this;
- obj.sign=x.sign=false;
- while( x.Cmp(obj,1) >0 )
- {
- k = x.len-obj.len;
- if( x.digital[x.len] > obj.digital[obj.len] )
- div =x.digital[x.len]/(obj.digital[obj.len]+1);
- else if(x.len>obj.len)
- {
- k--,
- div=(x.digital[x.len]*BASE+x.digital[x.len-1])/(obj.digital[obj.len]+1);
- }
- else break; //当x<=obj时跳出循环
- x-=(obj*(int)div).Shift(k);
- }
- if(x.Cmp(obj,1)>=0)x-=obj;
- if(x.Zero())x.sign = false;
- else x.sign=sign;
- return x;
- }
- BigInt& BigInt::operator >>=(int n)
- {
- if(n>1)
- *this>>=(n-1);
- if(digital[0]<=1&&len==0)digital[0] = 0;
- else
- {
- int k=len,t,carry=0;
- if (digital[k]==1)len--;
- while(k>=0)
- {
- t = digital[k]&1;
- digital[k]= digital[k]>>1;
- if(carry)digital[k]+=BASE/2;
- k--;
- carry = t;
- }
- }
- if(this->Zero())sign=0;
- return *this;
- }
- BigInt& BigInt::operator <<=(int n)
- {
- if(Zero())return *this;
- if(n>1)
- *this<<=(n-1);
- int k=0,t,carry=0;
- while(k<=len)
- {
- t=digital[k]<<1; //t最大值为(BASE-1)*2,不会溢出
- digital[k]=t%BASE;
- if(carry)digital[k]++;
- carry=t/BASE;
- k++;
- }
- if(carry)
- {
- digital[k]=1;len++;
- if(len>MAXN)
- {isLegal=false;return *this;}
- }
- return *this;
- }
- bool BigInt::Zero()const
- { return digital[0]+len==0;}
- qllong BigInt::FirSecDigit()
- {
- qllong temp=digital[len];
- if(len>0)
- return temp*BASE+digital[len-1];
- else
- return temp;
- }
- BigInt BigInt::Sqrt()
- {
- //本算法时间复杂度接近线性
- if(sign) //负数没有平方根
- {isLegal=false;return *this;}
- BigInt res,rem; //res保留的最终结果,rem保留余数
- qllong temp1,temp2;
- int temp,i;
- double r;
- bool flag;
- res.digital[0]=sqrt((double)digital[len]);
- rem.digital[0]=digital[len]-res.digital[0]*res.digital[0];
- for(i=len-1;i>=0;--i)
- {
- rem=rem.Shift(1),rem.digital[0]=digital;
- /*temp=(int)(rem/(res*20000)); */
- //此处的乘法不复杂,因为商为一个四位数,但是空间消耗很大,因此换用下面的方法
-
- flag=false;
- temp1=rem.FirSecDigit(); //获取大整数的前两位(16位)
- res=res*20000,temp2=res.FirSecDigit();
- if(temp1<temp2&&rem>res) //若temp1<temp2,则temp2除BASE
- {temp2/=BASE;flag=true;}
- temp=temp1/temp2;
- //下面两个条件语句用来精确temp,根据flag选择两种方式来逼近精确值
- if(flag)
- {while((res+temp)*temp>rem) //若单纯用temp--,对于有些情况下,效率会很差
- {temp--;}
- }
- else
- {for(r=0.6;(res+temp)*temp>rem;r+=0.1) //此处非常巧妙,逐渐增大权值,循环次数在5次之内
- {temp=temp1/(temp2+temp*r);} //并且当r==1时一定可以得到精确值
- while((res+(temp+1))*(temp+1)<rem)
- temp++;
- }
- rem-=((res+temp)*temp); //最终所得余数
- res=(res>>=1)+temp; //平方根的值,注意一定要加()
- }
- return res;
- }
- void BigInt::Factorial(int n)
- {
- this->sign=false;
- if(n<0){this->sign=true;n=-n;}
- int i,j,m=0;
- qllong carry;
- digital[0]=1;
- for(i=2;i<=n;i++)
- {
- for(j=0,carry=0;j<=m;j++)
- {
- carry+=digital[j]*i;
- digital[j]=carry%BASE;
- carry/=BASE;
- }
- if(carry)
- {
- if(m+1>=MAXN)
- {
- isLegal=false;
- return ;
- }
- digital[++m]=carry;
- }
- }
- len=m;
- }
- void BigInt::Factorial(int n, char c)
- {
- this->sign=false;
- if(n<0){this->sign=true;n=-n;}
- int i,j,m=0,work;
- qllong carry;
- if(n&1){work=digital[0]=1;}
- else {work=digital[0]=2;}
- for(i=work+2;i<=n;i+=2)
- {
- for(j=0,carry=0;j<=m;j++)
- {
- carry+=digital[j]*i;
- digital[j]=carry%BASE;
- carry/=BASE;
- }
- if(carry)
- {
- if(m+1>=MAXN)
- {
- isLegal=false;
- return ;
- }
- digital[++m]=carry;
- }
- }
- len=m;
- }
- BigInt BigInt::Shift(int k)
- {
- if(k==0||this->Zero())return *this;
- if(len+k>=MAXN){isLegal=false;return *this;}
- BigInt temp;
- int i;
- temp=*this;
- for(i=0;i<=len;i++)
- temp.digital[i+k]=digital;
- for(i=0;i<k;i++)
- temp.digital = 0;
- temp.sign=sign;
- temp.len=len+k;
- return temp;
- }
- int BigInt::Cmp(const BigInt &obj,bool Is_Abs)
- {
- //sign:1表示负数,0表示非负数
- if(!Is_Abs&&(obj.sign^sign))
- return (obj.sign-sign); //比较正负号
- int k=len-obj.len; //比较长度;
- if(k!=0)
- {
- if((k>0&&!sign)||(k<0&&sign))
- return 1;
- else
- return -1;
- }
- else
- {
- k=len;
- while(digital[k]==obj.digital[k]&&k>0)
- {--k;}
- if(digital[k]==obj.digital[k])
- return 0;
- if(Is_Abs)
- return digital[k]>obj.digital[k]?1:-1;
- else
- {
- if(digital[k]>obj.digital[k])
- return sign?-1:1;
- else
- return sign?1:-1;
- }
- }
- }
- void Swap(BigInt *num1,BigInt *num2)
- {
- BigInt temp;
- temp=*num1;
- *num1=*num2;
- *num2=temp;
- }
- QString BigInt::toQString()
- {
- QString qstr;
- if(sign==true)
- qstr.append('-');
- qstr.append(QString("%1").arg(digital[len]));
- for(int i=len-1;i>=0;i--)
- {
- qstr.append(QString("%1").arg(digital,8,10,QChar('0')));
- }
- return qstr;
- }
|