パーソナルインプリメンテーションの大数テンプレート(加算、乗算)
10769 ワード
現在大数の加算と乗算を実現し,いくつかのOJの問題をテストとして実現しているが,誤りがあれば多く指摘する.
#include <iostream>
#include <string>
#include <cstring>
/************************************************************************/
/* , 、 */
/************************************************************************/
class BigInteger{
public:
BigInteger():length(0),isNegative(false),digit(NULL){};
BigInteger(const std::string &num);
BigInteger(const BigInteger& old);
int getLength(void){return length;};
~BigInteger(){if(NULL != digit) delete []digit;};
friend std::ostream& operator<<(std::ostream&, const BigInteger&);
BigInteger& operator+=(const BigInteger& addend);
friend BigInteger operator+(const BigInteger&, const BigInteger&);
BigInteger& operator*=(const BigInteger& multiplier);
friend BigInteger operator*(const BigInteger&, const BigInteger&);
friend BigInteger operator*(const BigInteger&, const int);
friend BigInteger operator*(const int, const BigInteger&);
const int& operator[](const int t);
BigInteger& operator=(const BigInteger&);
BigInteger& operator=(const char*);
BigInteger& operator=(const std::string&);
BigInteger& operator=(const int);
private:
int length;
bool isNegative;
int* digit; //the smallest number storage in digit[0]
};
BigInteger::BigInteger(const std::string &num){
if(num[0] == '-'){
isNegative = true;
length = num.length() - 1;
}
else{
isNegative = false;
length = num.length();
}
digit = new int[length];
int i, numLen = num.length();
for(i = 0; i < length; i++){
digit[i] = num[numLen-1-i] - '0';
}
}
BigInteger::BigInteger(const BigInteger& old){
length = old.length;
isNegative = old.isNegative;
digit = new int[length];
int i;
for(i = 0; i < length; i++){
digit[i] = old.digit[i];
}
}
BigInteger& BigInteger::operator+=(const BigInteger& addend){//hadn't consider - this time
int maxLen = length > addend.length ? length : addend.length;
int* sum = new int[maxLen + 1];
int i, carry = 0;
for(i = 0; i < length && i < addend.length; i++){
sum[i] = digit[i] + addend.digit[i] + carry;
if(sum[i] >= 10){
sum[i] -= 10;
carry = 1;
}else{
carry = 0;
}
}
if(i >= length){
for(; i < addend.length; i++){
sum[i] = addend.digit[i] + carry;
if(sum[i] >= 10){
sum[i] -= 10;
carry = 1;
}else{
carry = 0;
}
}
}
else{
for(; i < length; i++){
sum[i] = digit[i] + carry;
if(sum[i] >= 10){
sum[i] -= 10;
carry = 1;
}else{
carry = 0;
}
}
}
if(carry){
sum[i] = carry;
delete []digit;
digit = sum;
length = maxLen + 1;
}
else{
delete []digit;
length = maxLen;
digit = new int[length];
for(i = 0; i < maxLen; i++){
digit[i] = sum[i];
}
delete []sum;
}
return *this;
}
BigInteger operator+(const BigInteger& a, const BigInteger& b){
BigInteger ans(a);
ans += b;
return ans;
}
BigInteger& BigInteger::operator*=(const BigInteger& multiplier){
isNegative = !(isNegative == multiplier.isNegative);
int maxLen = length + multiplier.length, ansLen = 0;
int *product = new int[maxLen];
int i, t;
memset(product, 0, sizeof(int)*maxLen);
for(i = 0; i < length; i++){
for(t = 0; t < multiplier.length; t++){
product[i+t] += digit[i]*multiplier.digit[t];
}
}
for(i = 0; i < maxLen-1; i++){
product[i+1] += product[i]/10;
product[i] %= 10;
}
ansLen = maxLen - 1;
while(ansLen > 0 && product[ansLen] == 0){
ansLen--;
}
length = ansLen + 1;
if(length == maxLen){
delete []digit;
digit = product;
}else{
delete []digit;
digit = new int[length];
int k;
for(k = 0; k < length; k++){
digit[k] = product[k];
}
delete []product;
}
return *this;
}
BigInteger operator*(const BigInteger& a, const BigInteger& b){
BigInteger ans(a);
ans *= b;
return ans;
}
const int& BigInteger::operator[](const int t){
if(NULL==digit || t>=length){
return -1;
}
else{
return digit[t];
}
}
std::ostream& operator<<(std::ostream& os, const BigInteger& b_int){
if(b_int.isNegative){
if(!(b_int.length==1 && b_int.digit[0]==0)){
os<<'-';
}//if b_int == 0 do not output -0
}
int i;
for(i = b_int.length-1; i >= 0; i--){
os<<b_int.digit[i];
}
return os;
}
BigInteger& BigInteger::operator=(const BigInteger& old){
if(this != &old){
length = old.length;
isNegative = old.isNegative;
delete []digit;
digit = new int[length];
int i;
for(i = 0; i < length; i++){
digit[i] = old.digit[i];
}
}
return *this;
}
BigInteger& BigInteger::operator=(const char* number){
if(number[0] != '-'){
isNegative = false;
length = strlen(number);
}
else{
isNegative = true;
length = strlen(number)-1;
}
if(digit != NULL) delete []digit;
digit = new int[length];
int i, numLen = strlen(number);
for(i = 0; i < length; i++){
digit[i] = number[numLen-1-i] - '0';
}
return *this;
}
BigInteger& BigInteger::operator=(const std::string& number){
if(number[0] != '-'){
isNegative = false;
length = number.length();
}
else{
isNegative = true;
length = number.length() - 1;
}
if(digit != NULL) delete []digit;
digit = new int[length];
int i, numLen = number.length();
for(i = 0; i < length; i++){
digit[i] = number[numLen-1-i] - '0';
}
return *this;
}
BigInteger& BigInteger::operator=(const int number){
isNegative = number < 0 ? true : false;
int tmp = number<0 ? -number : number;
length = 0;
do{
length++;
tmp /= 10;
}while(tmp);
if(NULL != digit){
delete []digit;
}
digit = new int[length];
tmp = number<0 ? -number : number;
int i = 0;
do{
digit[i++] = tmp%10;
tmp /= 10;
}while(tmp);
return *this;
}
int main(){
/*
//hdu1002
int t, k = 0;
std::cin>>t;
for(k = 1; k <= t; k++){
if(k != 1){
std::cout<<std::endl;
}
std::string str_a, str_b;
std::cin>>str_a>>str_b;
BigInteger a(str_a);
BigInteger b(str_b);
BigInteger ans(a);
ans = a + b;
std::cout<<"Case "<<k<<":"<<std::endl;
std::cout<<a<<" + "<<b<<" = "<<ans<<std::endl;
}
*/
/*
//hdu1715
BigInteger a[1001];
a[0] = "0";
a[1] = "1";
int t;
for(t = 2; t <= 1000; t++){
a[t] = a[t-1] + a[t-2];
}
int i, n;
std::cin>>n;
while(n--){
std::cin>>i;
std::cout<<a[i]<<std::endl;
}
*/
/*
//poj 1503
BigInteger ans, big;
ans = "0";
char num[120];
while(std::cin>>num){
if(num[0] == '0' && strlen(num)==1){
break;
}
big = num;
ans += big;
}
std::cout<<ans<<std::endl;
*/
/*
//poj 1001 unfinish====
BigInteger ans, big;
int n;
std::string num;
char *pnum;
while(std::cin>>num>>n){
big = num;
pnum = new char[num.length()];
int i, iDecimal;
for(i = 0; i < num.length){
}
ans = "1";
while(n){
if(n&1){
ans *= big;
}
big *= big;
n >>= 1;
}
std::cout<<ans<<std::endl;
}
*/
/*
//poj 2389
BigInteger ans, big;
std::string n1, n2;
std::cin>>n1>>n2;
ans = n1, big = n2;
ans *= big;
std::cout<<ans<<std::endl;
*/
/*
//poj 3331
const int MAXDAY = 367;
BigInteger factorial[MAXDAY];
int i;
factorial[0] = 1;
for(i = 1; i < MAXDAY; i++){
factorial[i] = i;
factorial[i] *= factorial[i-1];
}
int t, day, n, ans = 0;
std::cin>>t;
while(t--){
std::cin>>day>>n;
ans = 0;
for(i = 0; i < factorial[day].getLength(); i++){
if(factorial[day][i] == n){
ans++;
}
}
std::cout<<ans<<std::endl;
}
*/
/* //acm.zjut.edu.cn http://172.16.7.252/ShowProblem.aspx?ShowID=1027
BigInteger a, b;
std::string str_a, str_b;
while(std::cin>>str_a>>str_b){
a = str_a;
b = str_b;
a *= b;
std::cout<<a<<std::endl;
}*/
//acm.zjut.edu.cn http://172.16.7.252/ShowProblem.aspx?ShowID=1217
BigInteger a, b;
std::string str_a, str_b;
//char str_a[400], str_b[400];
while(std::cin>>str_a>>str_b){
if(str_a=="0" && str_b=="0"){
break;
}
if(str_a=="0" || str_b=="0"){
std::cout<<"0"<<std::endl;
continue;
}
a = str_a;
b = str_b;
a *= b;
std::cout<<a<<std::endl;
}/**/
}