仅自用

高精度计算

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
string add(string a,string b)//仅限两个非负整数相加
{
    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;
}

高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string sub(string a,string b)//仅限大的非负整数减小的非负整数
{
    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;
}

高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string mul(string a,string b)//a,b均为非负整数
{
    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';
    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;
}

高精度除以单精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string div(string a,int b)//高精度a除以单精度b
{
    string r,ans;
    int d=0;
    if(a=="0") return a;//特判
    for(int i=0;i<a.size();i++)
    {
        r+=(d*10+a[i]-'0')/b+'0';//求商
        d=(d*10+(a[i]-'0'))%b;//求余
    }
    int p=0;
    for(int i=0;i<r.size();i++)
    if(r[i]!='0') {p=i;break;}
    return r.substr(p);
}

快速幂模

快速幂

1
2
3
4
5
6
7
8
9
10
11
LL qPow(LL base, LL index)
{
    LL ans = 1;
    while (index)
    {
        if (index & 1) ans *= base;
        base *= base;
        index >>= 1;
    }
    return ans;
}