求A的B次方最后n位
- 正常求解发 一个循环累乘求解，但是幂运算都是爆发式增长，很有可能超出变量长度，即使是long long类型
幂运算法则
(1). (a + b) % p = (a % p + b % p) % p
(2). (a - b) % p = (a % p - b % p ) % p
(3). (a * b) % p = (a % p * b % p) % p
可以利用性质三
int n = 2;
int sum = 1;
for (int i = 0; i < 100; i++) {
sum = n * sum;
sum=sum % 1000;
}
算法时间复杂度为0（n）如果i过大，处理速度还是会很慢
优化:快速幂运算
幂的乘方公式：幂的乘方(a^m)^n=a^(mn)，与积的乘方(ab)^n=a^nb^n
观察可得，如果缩小指数大小就能减小乘法的次数，运用幂运算扩大底数
int sub = 2;
int num = 10;
int sum = 1;
while (num > 0) {
num = num / 2;
sub = sub * sub % 1000;
if ((num & 1) == 1) {
num = num - 1;
sum = sum * sub % 1000;
}
}