普通的函数写循环 时间就寄了 所以需要快速幂
已知(ab)%c=((a%c)(b%c))%c 可以初步优化 但是依然不够
核心思想就是每一步都把指数分成两半 而相应的底数做平方运算 如
3^10=3333333333
3^10=(33)(33)(33)(33)(33)
3^10=(33)^5
3^10=9^5
而当指数为奇数时 指数减一化为偶数
9^5=（9^4）（9^1）继续操作
9^5=（81^2）*(9^1)
9^5=（6561^1）*(9^1)
最后(9^1)(6561^1)=96561=59049
最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积

求a的b次方取余1000

[快速幂] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long long FastPower(long long base,long long power)
{
    long long result=1;
    while(power>0)
    {
        if (power % 2 == 0) {
            //如果指数为偶数
            power/=2;//把指数砍一半
            base=base*base%1000;//底数变大成原来的平方
    }   else{//如果是奇数
            power-=1;//先变成偶数
            result=result*base%1000;//独立出来的1必须记得
            power/=2;
            base=base*base%1000;
    }
    return result;
}

在此之外 可以再理解原理的基础上由向下取整简化

[快速幂] [c++]
1
2
3
4
power-=1;
power/=2;
等价于
power/=2;