UVA 10106 Product 簡單高精度乘法

題目要求輸入兩個非負的整數後求出他們的積

兩個數的範圍可以超出 long long型

第一次做高精度的題，這是我自己寫的AC代碼：

用字元串模拟乘法運算：

Result  :  Accepted     Memory  :  0 KB     Time :  16 ms

/*
 * Author: Gatevin
 * Created Time:  2014/7/3 16:12:18
 * File Name: test.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

string s1,s2;

int main()
{
   while(cin>>s1>>s2)
   {
       if(s1.length() == 1 && s1[0] == '0')//處理輸入有零的情況
       {
           cout<<"0"<<endl;
           continue;
       }
       if(s2.length() == 1 && s2[0] == '0')
       {
           cout<<"0"<<endl;
           continue;
       }
       reverse(s1.begin(), s1.end());//先将數字從末尾到首位擺放
       reverse(s2.begin(), s2.end());
       string ans(s1.length() + s2.length() + 1, '0');//兩個整數相乘，積的位數不會超過他們的位數和
       int c = 0;
       for(int i = 0; i < s1.length(); i++)//模拟乘法運算
       {
           c = 0;
           for(int j = 0; j < s2.length(); j++)
           {
              /*
               *一個數的倒數第i位乘上另一個數的倒數第j位改變的是倒數第i + j位(i,j是編号，從0開始)
               */
               int tmp1 =  ((ans[i + j] - '0') + (s1[i] - '0')*(s2[j] - '0') + c) / 10;
               int tmp2 =  ((ans[i + j] - '0') + (s1[i] - '0')*(s2[j] - '0') + c) % 10;
               ans[i + j] = tmp2 + '0';
               c = tmp1;
           }
           ans[i + s2.length()] += c;
       }
       int flag;
       for(int i = ans.length() - 1; i >= 0; i--)//輸出忽略前導零
       {
           if(ans[i] != '0')
           {
               flag = i;
               break;
           }
       }
       for(int i = flag; i >= 0; i--)
       {
           cout<<ans[i];
       }
       cout<<endl;
   }
   return 0;
}
           

這是之後使用高精度運算模闆的代碼：

Result  :  Accepted   Memory  : 0 KB   Time  :  13 ms

/*
 * Author: Gatevin
 * Created Time:  2014/7/4 12:58:26
 * File Name: test.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

struct bign
{
    int len,s[1000];
    bign()
    {
        len = 0;
        memset(s, 0 ,sizeof(s));
    }
    
    bign operator = (const char* num)
    {
        len = strlen(num);
        for(int i = 0; i < len; i++)
        {
            s[i] = num[len - i - 1] - '0';
        }
        return *this;
    }
    
    bign operator = (int num)
    {
        char s[1000];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }
    
    bign(int num)
    {
        *this = num;
    }
    
    bign(const char* num)
    {
        *this = num;
    }
    
    string str() const
    {
        string res = "";
        for(int i = 0; i < len; i++)
        {
            res = (char)(s[i] + '0') + res;
        }
        if(res == "")
        {
            res = "0";
        }
        return res;
    }
    
    bign operator + (const bign& b) const
    {
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; g || i < max(len, b.len); i++)
        {
            int x = g;
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    
    bign operator * (const bign& b) const
    {
        bign c;
        c.len = len + b.len;
        int k;
        for(int i = 0; i < len; i++)
        {
            k = 0;
            for(int j = 0; j < b.len; j++)
            {
                int tmp1 = (s[i] * b.s[j] + k + c.s[i + j]) / 10;
                int tmp2 = (s[i] * b.s[j] + k + c.s[i + j]) % 10;
                c.s[i + j] = tmp2;
                k = tmp1;
            }
            c.s[i + b.len] += k;
        }
        while(c.len > 1)
        {
            if(c.s[c.len - 1] == 0)
            {
                c.len--;
            }
            else
            {
                break;
            }
        }
        return c;
    }

    bign operator += (const bign& b)
    {
        *this = *this + b;
        return *this;
    }
    
    bool operator < (const bign& b) const
    {
        if(len != b.len) return len < b.len;
        for(int i = len - 1; i >= 0; i--)
        {
            if(s[i] != b.s[i])
            {
                return s[i] < b.s[i];
            }
        }
        return false;
    }
};


    istream& operator >> (istream &in, bign & x)
    {
        string s;
        in >> s;
        x = s.c_str();
        return in;
    }
    
    ostream& operator << (ostream & out, const bign& x)
    {
        out << x.str();
        return out;
    }


int main()
{
    bign x1,x2;
   while(cin>>x1>>x2)
  cout<<x1*x2<<endl; 
    return 0;
}
           

模闆代碼我沒加注釋，不懂的話可以看看我之後整理的 bign 模闆