[随笔] 快速幂

没办法老师让预习，我就只能把我快一年前的快速幂翻出来

不放洛谷了，老师容易窥探＞﹏＜

老师の问题

1.快速幂的原理是什么

每一步都把指数分成两半，而相应的底数做平方运算

2.如果求2的23次方，快速幂的具体过程是什么

∵23=2^0+2^1+2^2+2^4

∴2^23=2^2^0 * 2^2^1 * 2^2^2 * 2^2^4

位运算

 1 long long ksm(int n,int x){
 2     int ans=1;
 3     while(x){
 4         if(x&1){
 5             ans*=n;
 6         }
 7         n*=n;
 8         x>>=1;
 9     }
10     return ans;
11 }

递归

 1 long long ksm(int n,int x){
 2     if(x==0) 
 3         return 1;
 4     else if (n%2==1){
 5         return ksm(n,x-1)*n;
 6     }
 7     else{
 8         int temp=ksm(n,x/2);
 9         return temp*temp;
10     }
11 }