十进制快速幂

$十进制快速幂$十进制快速幂

使用快速幂求 $a^b$ab, 当 $b$b很大的时候, 就需要使用十进制快速幂

十进制快速幂

$a^b$ab中 $b$b可以分解为 $k_{n}10^n+k_{n-1}10^{n-1}+...+k_1$kn​10n+kn−1​10n−1+...+k1​
则可以得到 $a^b=a^{k_{n}10^n}\ast a^{k_{n-1}10^{n-1}}\ast .....a^{k_1}$ab=akn​10n∗akn−1​10n−1∗.....ak1​
在十进制快速幂中, 将 $a^1$a1作为基底, 采用从低位到高位处理的办法, 对于每个位数上的数字, 只要有 $a^2,a^3,a^4$a2,a3,a4, 即可凑出所有 $10$10以内的所有幂数, 在进入下一个更高位的时候, 将当前基底 $a^b$ab -> $a^{b\ast 10}$ab∗10即可

我们以 求 $2^{N-1}\ast N$2N−1∗N 为例子得到以下代码
在代码中有 $KS{M}_1$KSM1​和 $KS{M}_2$KSM2​两个函数, 作用是一样的, 其中1的效率比2更快, 大概 $1/3$1/3

Code

#include<bits/stdc++.h>
#define reg register

typedef long long ll;

const int mod = 1e9;
const int maxn = 1e7+5;

char S[maxn];
int Len;

ll KSM(ll a, ll b){
        ll s = 1;
        while(b){
                if(b & 1) s = s*a % mod;
                a = a*a % mod;
                b >>= 1;
        }
        return s;
}

ll KSM_1(ll a){
        ll s = 1;
        for(reg int i = 1; i <= Len; i ++){
                ll t2 = a*a % mod;
                ll t3 = t2 * a % mod;
                ll t4 = t3 * a % mod;
                ll t5 = t4 * a % mod;
                if(S[i] == '1') s = s * a % mod;
                else if(S[i] == '2') s = s * t2 % mod;
                else if(S[i] == '3') s = s * t3 % mod;
                else if(S[i] == '4') s = ((s*a % mod) * t3) % mod;
                else if(S[i] == '5') s = ((s*t2 % mod) * t3) % mod;
                else if(S[i] == '6') s = ((s*t3 % mod) * t3) % mod;
                else if(S[i] == '7') s = ((s*t3 % mod) * t4) % mod;
                else if(S[i] == '8') s = ((s*t4 % mod) * t4) % mod;
                else if(S[i] == '9') s = ((s*t4 % mod) * t5) % mod;
                a = t5 * t5 % mod;
        }
        return s;
}

ll KSM_2(ll a){
        ll s = 1;
        for(reg int i = 1; i <= Len; i ++){
                int p = S[i] - '0';
                while(p --) s = s * a % mod;
                p = 9;
                ll tmp = a;
                while(p --) a = a * tmp % mod;
        }
        return s;
}

int main(){
        scanf("%s", S+1);
        Len = strlen(S+1);
        ll Temp = 0;
        for(reg int i = 1; i <= Len; i ++) Temp = (Temp*10+S[i]-'0') % mod;

        std::reverse(S+1, S+Len+1);
        int t = 1;
        while(S[t] == '0') S[t ++] = '9';
        S[t] --;
        if(S[Len] == '0') Len --;
        //printf("%lld\n", Temp);
        printf("%lld\n", KSM_2(2) * Temp % mod);
        return 0;
}

既然有十进制快速幂, 肯定会有十进制矩阵快速幂,道理是一样的, 代码如下

Code

#include<cstdio>
#include<cstring>
#include<algorithm>

const int mod = 998244353;

int L;
char N[4005];

namespace mt{   
    struct matrix{
        int C[10][10];
        matrix(){ memset(C, 0, sizeof C); }
    };

    matrix mdf(matrix a, matrix b){
        matrix s;
        for(int i = 1; i <= 6; i ++)
            for(int j = 1; j <= 6; j ++)
                for(int k = 1; k <= 6; k ++)
                    (s.C[i][k] += (long long)a.C[i][k] * b.C[k][i] % mod) %= mod;
        return s;
    }

    matrix Counting(matrix a){
        matrix s;
        for(int i = 1; i <= 6; i ++) s.C[i][i] = 1;
        while(L --){
            matrix B = mdf(a, a);   //a^2
            matrix C = mdf(B, a);   //a^3
            matrix D = mdf(C, a);   //a^4
            switch(N[L]){
                case '1':{ s = mdf(s, a); break ; }
                case '2':{ s = mdf(s, B); break ; }
                case '3':{ s = mdf(s, C); break ; }
                case '4':{ s = mdf(s, D); break ; }
                case '5':{ s = mdf(mdf(D, a), s); break ; }
                case '6':{ s = mdf(mdf(B, D), s); break ; }
                case '7':{ s = mdf(mdf(C, D), s); break ; }
                case '8':{ s = mdf(mdf(D, D), s); break ; }
                case '9':{ s = mdf(mdf(mdf(D, a), D), s); break ; }
            }
            a = mdf(mdf(mdf(a, D), D), B);
        }
        return s;
    }
}

mt::matrix I;

int main(){
    scanf("%s", N + 1);
    L = strlen(N + 1);
    if(L == 1 && N[L] <= '4')
        switch(N[L]){
            case '1':{ puts("1"); return 0; }
            case '2':{ puts("3"); return 0; }
            case '3':{ puts("10"); return 0; }
            case '4':{ puts("23"); return 0; }
        }

    return 0;
}