题目描述

高精乘高精（均为正数）

样例

712896413287946723467892637846327164713243671294623146732614623146287193637812647672138467216489632764378267826764873216433629871267128964132879467234678926378463271647132436712946231467326146231462871936378126476721384672164896327643782678267648732164336298712671289641328794672346789263784632716471324367129462314673261462314628719363781264767213846721648963276437826782676487321643362987126
698764298671892367891236879342689541285189327632671268796142387964728167128967891268791264879698764298671892367891236879342689541285189327632671268796142387964728167128967891268791264879698764298671892367891236879342689541285189327632671268796142387964728167128967891268791264879
498146562256859623270650475898139777068926529766946682640635818456130809420673599405538077689767552442285009210863050075481349817353049058724052475229504407386838475012461671588623737831478065884944606067338001178830060071785743117524333971105428403382670575415302896878194795756868605211994823099985231424762776896133921722183983257029542095960026868538956238060659533026358439291924994516420745931513020575485415401644050091222783387717860822278698581403383701760874747360194730607699794828164310321052721342843768595346859391722028721875857356113812643834986061470887653951781914106333453719635616208417172626782109880688541619331530415525809828876226821510929332947754

算法1

(高精乘) $O(n)$

blablabla

时间复杂度o(n)

参考文献

C++ 代码

#include<iostream>
#include<vector>
using namespace std;

vector<int> mul(vector<int>&A,vector<int>&B)
{
    vector<int>C(A.size()+B.size(),0);
    for(int i=0;i<A.size();++i){
        int t=0;
        for(int j=0;j<B.size();++j)
        {
            t+=C[i+j]+A[i]*B[j];
            C[i+j]=t%10;
            t/=10;
        }
        if(t>0){
            C[i+B.size()]+=t;
        }
    }
    while(C.size()>1&&C.back()==0)C.pop_back();
    return C;
}

int main(){
    string a,b;
    cin>>a>>b;
    vector<int>A,B;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');

    auto C=mul(A,B);
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    cout<<endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla