十进制快速幂

十进制快速幂

例：求a^b%mod,(a<=10,b<=1e100000,mod=1e9+7)

说明

这时候 long long是存不下b的，但是可以用字符数组存；

举个简单例子，求 2^2345；

可以依次求2^2 -> (2^2)^10=2^20 -> (2^20)^3=2^23 -> (2^23)^10=2^230 -> (2^230)^4 -> (2^234)^10=2^2340 -> (2^2340)^5=2^2345

上代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define maxn 100007
 5 #define mod 1000000007
 6 int bit[15];
 7 char b[maxn];
 8 ll qpow(ll a,ll b,ll m)//快速幂
 9 {
10     ll ans=1;
11     while(b)
12     {
13         if(b&1)ans=ans*a%m;
14         a=a*a%m;
15         b>>=1;
16     }
17     return ans%m;
18 }
19 int main()
20 {
21     ll a;
22     cin>>a>>b;
23     bit[0]=1;
24     for(int i=1;i<10;i++)//打表,bit[i]表示a^i
25     {
26         bit[i]=bit[i-1]*a%mod;
27     }
28     ll ans=1;
29     int len=strlen(b);
30     for(int i=0;i<len;i++)
31     {
32         ans=ans*bit[n[i]-'0']%mod;//求ans^(b[i]-'0')
33         if(i<len-1)ans=qpow(ans,10,mod)%mod;//求ans^10
34     }
35     printf("%lld
",ans);
36     return 0;
37 }