w22116972
4/1/2014 - 5:52 AM

大數乘法

大數乘法

#include <string>
#include <algorithm>

string operator* (string& a , string& b){
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    
    for (int i=0; i<a.size(); i++)
        a[i]-='0';
    for (int i=0; i<b.size(); i++)
        b[i]-='0';

    string ans (a.size()+b.size(),0);
    
    for (int i=0; i<a.size(); i++) {
        for (int j=0; j<b.size(); j++)
            ans[i+j]+=a[i]*b[j];
        for (int k=0; k<ans.size(); k++) {
            if (ans[k]>=10) {
                ans[k+1]+=ans[k]/10;
                ans[k]%=10;
            }
        }
    }
    
    int length=int(ans.size());
    while (length && ans[length-1]==0)
        length--;
    ans.resize(length);
    for (int i=0; i<ans.size(); i++)
        ans[i]+='0';
    if (ans.size()==0)
        ans="0";
    reverse(ans.begin(), ans.end());

    return ans;
}