k进制快速幂

快速幂简述

　　通常快速求a^b （常常还会要求取模，这样的话只要边乘边模即可）时，我们一般将指数b转换成二进制，然后从低位到高位“扫描”，并维护一个代表该位权值的伴随变量。根据该位是否为1来决定是否给维护的答案变量乘上该位的权值。只要扫描log₂ n位，扫描每位时只做常数次以内的运算（伴随变量、答案变量的更新，指数位的移动），故复杂度为log₂b。

 1 #define ll long long
 2 ll Pow( ll a,ll b,ll mod )
 3 {
 4     ll ans = 1,w = a;
 5     while( b >= 0 )
 6     {
 7         if(b & 1)
 8           ans = ans * w % mod;
 9         w = w * w % mod;b >>= 1;            //看下一位
10     }
11     return ans;
12 }

二进制快速幂函数

　　但是当b特别大（如b<=10^1000000）时，要存下b就要用字符串/高精度，难以从二进制的角度直接处理b。要么用高精度进制转换（n^2复杂度警告，n为转换结果数的位数），要么头铁做k（视实际情况。这里以10进制读入，就取k=10）进制快速幂。

k进制快速幂

　　在k进制下不进行进制转换，直接从指数b的低位开始扫描做快速幂。维护答案变量和代表该位权值的伴随变量，该位为几，就给答案变量乘几次伴随变量。

 1 //默认k为比较小的数。 
 2 #define ll long long 
 3 char c[ 1000007 ];//字符串存大整数，这里存的是指数，顺序存储（c[0]存最高位） 
 4 ll kthPow( ll a,ll t,ll mod,ll k )//t为指数的位数 
 5 {
 6     ll ans = 1,w = a;
 7     while( t >= 0 ){
 8         ll cnt = c[ t ] - '0';
 9         for( int i = 1 ; i <= cnt ; ++i )
10           ans = ans * w % mod;
11          //和二进制快速幂不同的地方之一 ** 
12         ll cur=w; 
13         for( int i = 1 ; i < k ; ++i )
14           w = w * cur % mod;//求伴随变量进到下一位后的权值，即求伴随变量的k次幂  **
15         //注意因为自身就是1次幂所以只乘k-1次。 
16         --t;
17     }
18     return ans;
19 }

　　时间复杂度为 k*log_k b 一般来说k不会很大。如果遇到k也很大的情况，可以在上文注释标记**处的for循环改为缀套的快速幂，复杂度log₂ k（总不会k也不能被longlong存下吧。能被存缀套的快速幂就用普通二进制的就行了呗，方便写代码） log _k b

参考博客：

十进制快速幂算法