?? 高精度庫.cpp
字號:
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
using namespace std;
int const MAX = 300;
class BigInt
{
public:
int data[MAX]; //用于存放該萬進制數
int num; //該數有多少位
bool neg; //是否負數
public:
void assign(const string &s); //f1: 用string型給BigInt賦值
void assign(int n); //f2: 用int型給BigInt賦值
//f3: 輸出BigInt值,副作用輸出該BigInt的輸出流被setfill('0')
friend ostream & operator << (ostream & outf, const BigInt &a);
BigInt(BigInt &b); //f4: 拷貝構造函數,可以用'='給BigInt賦BigInt值,需要加上上面的構造函數
BigInt(int a = 0){assign(a);} //f5: 構造函數
void operator -() {if(!this->is_zero()) neg = !neg;} //f6: 對該對象取負
bool is_zero() {return data[num - 1] == 0;} //f7: 判斷是否為0
void operator += (BigInt &a); //f11: 給當前BigInt 加上一個BigInt
void operator += (int a){BigInt temp(a); *this += temp;} //f12: 給當前BigInt 加上一個int
BigInt operator + (BigInt &a) {BigInt temp = *this; temp += a; return temp;} //f13: 兩個BigInt相加
BigInt operator + (int a) {BigInt temp = *this; temp +=a; return temp;} //f14: BigInt與int相加
void operator -= (BigInt &a) {neg = !neg; *this += a; neg = !neg;}//f15: 給當前BigInt減去一個BigInt
void operator -= (int a) {BigInt temp(a); *this -= temp;} //f16: 給當前BigInt減去一個int
BigInt operator - (BigInt &a) {BigInt temp = *this; temp -= a; return temp;} //f17: 兩個BigInt相減
BigInt operator - (int a) {BigInt temp = *this; temp -= a; return temp;} //f18: BigInt與int相加
bool operator > (BigInt &a) {int i = Less(this, &a); return i == -1;} //f20: 判斷a是否大于b
bool operator >= (BigInt &a) {int i = Less(this, &a); return i != 1;} //f21: 判斷a是否大于等于b
bool operator < (BigInt &a) {int i = Less(this, &a); return i == 1;} //f22: 判斷a是否小于b
bool operator <= (BigInt &a) {int i = Less(this, &a); return i != -1;} //f23: 判斷a是否小于等于b
bool operator == (BigInt &a) {int i = Less(this, &a); return i == 0;} //f24: 判斷a是否等于b
bool operator != (BigInt &a) {int i = Less(this, &a); return i != 0;} //f25: 判斷a是否不等于b
void operator *= (int a) {Positive_mul(this, abs(a)); neg = neg != a<0; if(a == 0) neg = false;} //f28: 給當前BigInt乘以int a
//f29: 給當前BigInt乘以Bigint a
void operator *= (BigInt & a) {Positive_mul(this, &a); neg = neg != a.neg; if(a.is_zero()) neg = false;}
BigInt operator * (int a) {BigInt temp = *this; temp *= a; return temp;} //f30: BigInt乘以int a
BigInt operator * (BigInt &a) {BigInt temp = *this; temp *= a; return temp;} //f31: BigInt乘以Bigint
void operator /= (int a) {BigInt r, temp(a); div(*this, temp, r);} //f34: BigInt除等于int
void operator /= (BigInt a) {BigInt r; div(*this, a, r);} //f35: BigInt除等于BigInt
void operator %= (int a) {BigInt r, temp(a); div(*this, temp, r); *this = r;} //f36: BigInt對int取余
void operator %= (BigInt a) {BigInt r; div(*this, a, r); *this = r;} //f37:
BigInt operator / (int a) {BigInt r,temp = *this, t(a); div(temp, t, r); return temp;} //f38:
BigInt operator / (BigInt a) {BigInt r, temp = *this; div(temp, a, r); return temp;} //f39:
BigInt operator % (int a) {BigInt r,temp = *this, t(a); div(temp, t, r); return r;} //f40:
BigInt operator % (BigInt a) {BigInt r, temp = *this; div(temp, a, r); return r;} //f41:
/*******************************************************************************************/
//f8: 把BigInt b*10000^zero_after_b加到a上
friend void Positive_add(BigInt *a, BigInt *b, int zero_after_b = 0);
friend int Positive_less(BigInt *a, BigInt *b); //f9: 比較兩個BigInt有效位的大小,1:小于,-1:大于,0:等于
friend void Positive_minus(BigInt *big, BigInt *small); //f10: 對BigInt big減去small,大正數減小正數
friend int Less(BigInt *a, BigInt *b); //f19: 比較兩個BigInt的大小,1:小于,0:大于,-1:等于
friend void Positive_mul(BigInt *a, int b); //f26: 非負BigInt乘等于int, 0<=int<10000
friend void Positive_mul(BigInt *a, BigInt *b); //f27: 非負BigInt乘等于BigInt
friend void Positive_div(BigInt &a, BigInt &divisor, BigInt &remainder); //f32: 帶余非負數相除, b != 0
friend void div(BigInt &a, BigInt &divisor, BigInt &remainder); //f33: BigInt相除
};
/*******************************************************************************************/
/*------------------------------f1: 用string型給BigInt賦值--------------------------------*/
void BigInt::assign(const string &s)
{
neg = (s[0] == '-');
num = 0;
data[0] = 0;
int j = 0;
int t = 1;
for(int i = s.size() - 1; i >= neg; i--)
{
j++;
data[num] += (s[i] - '0') * t;
t *= 10;
if(j%4 == 0)
{
num++;
data[num] = 0;
t = 1;
}
}
if(j%4)
num++;
}
/*---------------------------f2: 用int型給BigInt賦值--------------------------------------*/
void BigInt::assign(int n)
{
neg = false;
if(n < 0)
{
neg = true;
n *= -1;
}
num = 0;
while(n / 10000)
{
data[num++] = n % 10000;
n /= 10000;
}
data[num++] = n;
}
/*---------------f3: 輸出BigInt值,副作用輸出該BigInt的輸出流被setfill('0')----------------*/
ostream & operator << (ostream &outf, const BigInt &a)
{
if(a.neg)
outf<<'-';
int i = a.num - 1;
outf<<a.data[i];
outf<<setfill('0');
while(i > 0)
outf<<setw(4)<<a.data[--i];
return outf;
}
/*----------f4: 拷貝構造函數,可以用'='給BigInt賦BigInt值,需要加上上面的構造函數-----------*/
BigInt::BigInt(BigInt &b):neg(b.neg),num(b.num)
{
for(int i = 0; i < num; i++)
data[i] = b.data[i];
//cout<<"Copy constructor Called"<<endl;
}
/*-------------------f8: 把BigInt b*10000^zero_after_b加到a上-------------------*/
void Positive_add(BigInt *a, BigInt *b, int zero_after_b)
{
if(b->is_zero())
return;
//把該數據可能即將用到的數據進行初始化為0
a->data[a->num] = 0;
int i, bnum = b->num + zero_after_b;
for(i = a->num + 1; i < bnum + 1; i++)
a->data[i] = 0;
//把b的數據加到該數據上,不進位
for(i = 0; i < b->num; i++)
a->data[i + zero_after_b] += b->data[i];
//控制進位
int num1 = (bnum > a->num) ? bnum : a->num;
int teamp = 0; //暫時存放進位
for(i = 0; i < num1; i++)
{
a->data[i] += teamp;
teamp = a->data[i] / 10000;
a->data[i] %= 10000;
}
if(teamp)
{
a->data[a->num] = teamp;
a->num = num1 + 1;
}
else
a->num = num1;
}
/*------------------------f9: 比較兩個BigInt有效位的大小,1:小于,-1:大于,0:等于-------------------*/
int Positive_less(BigInt *a, BigInt *b)
{
if(a->num > b->num)
return -1;
if(a->num < b->num)
return 1;
for(int i = b->num - 1; i >= 0 ; i--)
if(a->data[i] < b->data[i])
return 1;
else if(a->data[i] > b->data[i])
return -1;
return 0; //表示等于
}
/*------------------------------f10: 對BigInt big減去small,大正數減小正數-------------------------*/
void Positive_minus(BigInt *big, BigInt *small)
{
for(int i = 0; i < small->num; i++)
{
if(big->data[i] < small->data[i])
{
big->data[i + 1] --;
big->data[i] += 10000;
}
big->data[i] -= small->data[i];
}
while(!big->data[big->num - 1])
big->num --;
if(big->num == 0) big->num = 1;
if(big->is_zero())
big->neg = false;
}
/*-------------------------------f11: 給當前BigInt 加上一個BigInt--------------------------------*/
void BigInt::operator +=(BigInt &a)
{
if(!neg && a.neg)
if(Positive_less(this, &a) == 1)
{
BigInt temp = a;
Positive_minus(&temp, this);
*this = temp;
neg = true;
}
else
Positive_minus(this, &a);
else if(neg && !a.neg)
{
if(Positive_less(this, &a) == 1)
{
BigInt temp = a;
Positive_minus(&temp, this);
*this = temp;
neg = false;
}
else
{
Positive_minus(this, &a);
neg = true;
}
}
else
Positive_add(this, &a); //只加有效位,符號不動
}
/*--------------------------f19: 比較兩個BigInt有效位的大小,1:小于,-1:大于,0:等于------------------------*/
int Less(BigInt *a, BigInt *b)
{
int i = Positive_less(a, b);
if(!a->neg && !b->neg)
return i;
if(a->neg && b->neg)
return - i;
if(a->neg && !b->neg)
return 1;
if(!a->neg && b->neg)
return -1;
}
/*------------------------------f26: BigInt乘等于int, 0<=int<10000 -----------------------------*/
void Positive_mul(BigInt *a, int b)
{
if(b == 0)
{
a->assign(0);
return;
}
//不進位乘法
for(int i = 0; i < a->num; i++)
a->data[i] *= b;
//進位
int t = 0;
for(int j = 0; j < a->num; j++)
{
a->data[j] += t;
t = a->data[j] / 10000;
a->data[j] %= 10000;
}
if(t)
a->data[a->num++] = t;
}
/*----------------------------------f27: 非負BigInt乘等于BigInt----------------------------------*/
void Positive_mul(BigInt *a, BigInt *b)
{
BigInt result;
for(int i = 0; i < b->num; i++)
{
BigInt temp = *a;
temp *= b->data[i];
Positive_add(&result, &temp, i);
}
bool boo = a->neg;
*a = result;
a->neg = boo;
}
/*---------------------------------f32: 帶余非負數相除, b != 0------------------------------*/
void Positive_div(BigInt &a, BigInt &b, BigInt &r)
{
//if(b.is_zero()) cout<<"Dived by zero!"<<endl;
if(a < b){r = a; a.assign(0); return;}//處理特殊情況
int n = a.num - b.num + 1; //結果的位數，可能多一位
r.assign(0);
r.num = b.num - 1;
for(int i = 0; i < r.num; i++)
r.data[i] = a.data[n + i];
if(b.num == 1) //處理b只有一位的特殊情況
r.num = 1;
for(int i = n - 1; i >= 0; i--)
{
r *= 10000;
r += a.data[i];
a.data[i] = 0;
while(b <= r)
{
int header = r.data[r.num - 1];
if(r.num > b.num)
header = header * 10000 + r.data[r.num - 2];
int part_quotient = header/(b.data[b.num - 1] + 1);
if(part_quotient < 1)
part_quotient = 1; //以上6行是“保守試商”的過程
BigInt temp = b;
temp *= part_quotient;
r -= temp;
a.data[i] += part_quotient;
}
}
a.num = n;
while(a.data[a.num - 1] == 0)
a.num --;
}
/*--------------------------------------f33: BigInt相除--------------------------------------------*/
void div(BigInt &a, BigInt &divisor, BigInt &remainder)
{
bool temp = a.neg != divisor.neg;
divisor.neg = false;
a.neg = false;
Positive_div(a, divisor, remainder);
if(temp)
{
-a;
-remainder;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -