biginteger.cpp

Sicily 1198题 SubString 源代码

#include <deque>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

class DividedByZeroException {};

class BigInteger
{
    private:
        vector<char> digits;         
    public:
        BigInteger(int);    // construct with a int integer
        BigInteger(string&) ;
        BigInteger();
        BigInteger (const BigInteger&);
        BigInteger operator=(const BigInteger& op2);

        //binary operators

        friend BigInteger operator+=(BigInteger&,const BigInteger&);      
        
        //uniary operators      
        friend ostream& operator<<(ostream&,const BigInteger&);    //print the BigInteger
        friend istream& operator>>(istream&, BigInteger&);         // input the BigInteger

public:
        static const BigInteger ZERO;
        static const BigInteger ONE;
        static const BigInteger TEN;
};

 const BigInteger BigInteger::ZERO=BigInteger(0);
 const BigInteger BigInteger::ONE =BigInteger(1);
 const BigInteger BigInteger::TEN =BigInteger(10);

BigInteger::BigInteger()
{
}

BigInteger::BigInteger(int val){// construct with a int integer    
    do{
        digits.push_back( (char)(val%10) );
        val /= 10;
    } while ( val != 0 );
}

BigInteger::BigInteger(string& def){
    for ( string::reverse_iterator iter = def.rbegin() ; iter < def.rend();  iter++){
        digits.push_back( (char)((*iter) - '0' ) );
    }
}

BigInteger::BigInteger(const BigInteger& op2){
    digits=op2.digits;
}

BigInteger BigInteger::operator=(const BigInteger& op2){
            digits = op2.digits;
            return (*this);
 }

//binary operators
BigInteger operator+=(BigInteger& op1,const BigInteger& op2){
        vector<char>::iterator iter1;
        vector<char>::const_iterator iter2;
        iter1 = op1.digits.begin();
        iter2 = op2.digits.begin();
        char to_add = 0;        //进位
        while ( iter1 != op1.digits.end() && iter2 != op2.digits.end()){
            (*iter1) = (*iter1) + (*iter2) + to_add;
            to_add = ((*iter1) > 9);    // 大于9进一位
            (*iter1) = (*iter1) % 10;
            iter1++; iter2++;
        }
        while ( iter1 != op1.digits.end() ){   //
            (*iter1) = (*iter1) + to_add;
            to_add = ( (*iter1) > 9 );
            (*iter1) %= 10;
            iter1++;
        }
        while ( iter2 != op2.digits.end() ){
            char val = (*iter2) + to_add;
            to_add = (val > 9) ;
            val %= 10;
            op1.digits.push_back(val);
            iter2++;
        }
        if( to_add != 0 )
            op1.digits.push_back(to_add);
        return op1;
}

//uniary operators
ostream& operator<<(ostream& stream,const BigInteger& val)
{    
    for ( vector<char>::const_reverse_iterator iter = val.digits.rbegin(); iter != val.digits.rend() ; iter++)
        stream << (char)((*iter) + '0');
    return stream;
}

istream& operator>>(istream& stream, BigInteger& val)
{    //Input the BigInteger
    string str;
    stream >> str;
    val=BigInteger(str);
    return stream;
}

int main()
{
    int m, d, i, j;
    while(true)
    {
        BigInteger r[101] = {0}, sum = 0;
        cin >> m;
        cin >> d;
        if(m == 0 && d == 0)
            break;

        for(i = 0; i <= d; i++)
        {
            if(i <= m)
                r[i] = 1;
            else
                for(j = 0; j <= i - m; j++)
                   r[i] += r[j];
            sum += r[i];
        }
        cout << sum << endl;
    }
    return 0;
}