快速幂

快速幂
这个先上Code吧

int power(int x, int y) {
    int sum = 1;
    while(y) {
        if(y & 1) sum *= x;
        x *= x;
        y >>= 1;
    }
    return sum;
}

众所周知\(p^a * p^b=p^{a+b}\)
我们现在需要求\(x^y\)
举个栗子，我们求\(3^5\)
我们把\(5\)拆成二进制\(101\)
可以发现正正好的在二进制下的位数只要是\(1\)的乘起来就是答案
emmmm，可能我说的不是特别的严密
就是\(3^5=3^{1*2^0+0*2^1+1*2^2}\)
把有\(0\)的一项直接去掉
\(3^5=3^{1*2^0+1*2^2}\)
也就是\(3^{2^0} * 3^{2^2}\)
\(3\)每次自乘可以得到\(3^1,3^2,3^4,3^8......\)
所以求3的几次方是几就不是问题了
只要是在二进制下是1的我们就累计答案让
一般题目是要取膜的因为指数级别增长数会非常大

没了，讲完了
谢谢收看，祝身体健康！