高精度テンプレート

なぜ高精度が必要なのですか?intでもlong longでも格納できる桁数には制限があるからです.特に大きな数に直面するとオーバーフローが発生します.そのため、任意の長さの数字を保存する方法が必要です.配列は私たちが問題を解決する鍵です.

の高精度な実装には、一般にstring、またはint[](int型配列)がある.int[]を使用すると、4つの数字から8つの数字をintに入れることで、

の保存効率を向上させることができます.

高精度加算

入力パラメータはいずれもstringタイプであり、戻り値はstringタイプ

である.

アルゴリズム思想:逆加算再還元.

アルゴリズム複雑度:o(n)

string add(string a,string b)//          
{
    const int L=1e5;
    string ans;
    int na[L]={0},nb[L]={0};
    int la=a.size(),lb=b.size();
    for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
    for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
    int lmax=la>lb?la:lb;
    for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;
    if(na[lmax]) lmax++;
    for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
    return ans;
}

2.高精度減算

入力パラメータはいずれもstringタイプであり、戻り値はstringタイプ

である.

アルゴリズム思想:逆転相減再還元.

アルゴリズム複雑度:o(n)

string sub(string a,string b)//               
{
    const int L=1e5;
    string ans;
    int na[L]={0},nb[L]={0};
    int la=a.size(),lb=b.size();
    for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
    for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
    int lmax=la>lb?la:lb;
    for(int i=0;i<lmax;i++)
    {
        na[i]-=nb[i];
        if(na[i]<0) na[i]+=10,na[i+1]--;
    }
    while(!na[--lmax]&&lmax>0)  ;lmax++;
    for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
    return ans;
}

高精度乗算

入力パラメータはいずれもstringタイプであり、戻り値はstringタイプ

である.

アルゴリズム思想:逆転乗算し、その後、進位を統一的に処理し、復元する.

アルゴリズム複雑度:o(n^2)fftを用いて時間複雑度O(nlogn)

を最適化することもできる

string mul(string a,string b)//     a,b,      
{
    const int L=1e5;
    string s;
    int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();//na     ，nb    ，nc   
    fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);// na,nb,nc   0
    for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';//             i           
    for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';
    for(int i=1;i<=La;i++)
        for(int j=1;j<=Lb;j++)
        nc[i+j-1]+=na[i]*nb[j];//a  i   b  j     i+j-1 （      ）
    for(int i=1;i<=La+Lb;i++)
        nc[i+1]+=nc[i]/10,nc[i]%=10;//      
    if(nc[La+Lb]) s+=nc[La+Lb]+'0';//   i+j        0
    for(int i=La+Lb-1;i>=1;i--)
        s+=nc[i]+'0';//          
    return s;
}

兄貴に書いた.