[算法]—快速幂算法及优化

普通求幂算法

我们先来看一道例题 hdu 2035

人见人爱A^B

题目描述

求A^B的最后三位数表示的整数。 说明：A^B的含义是“A的B次方”

Input

输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。

Output

对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。

Sample Iutput

2 3 12 6 6789 10000 0 0

Sample Output

8 984 1

解题思路：最简单的思路应该是讲数据求出然后对1000取余求出最后3位数字，我们都听说过指数爆炸这个概念吧，结果会随着指数增加而爆炸式增长，而且6789的10000次方即使long long 类型也存不下，下面我们先来介绍一组数学公式

(a + b) % c = ((a%c) + (b%c)) % c a * b % c = ( (a%c) * (b%c) ) % c a / b % c = ((a%c) / (b%c)) %c 所以我们可以对每个因子进行取模运算，从而减小数据大小 下面为C语言代码

#include <stdio.h>

long long quit(long long x, long long y)
{
          
   
    long long  ans = 1;
    for(int i = 1; i <= y; i++)
    {
          
   
        ans *= x;
        ans = ans%1000;
    }
    return ans%1000;
}
int main(void)
{
          
   
    long long a, b, ans;
    while(~scanf("%lld%lld", &a, &b))
    {
          
   
        if(a == 0 && b == 0) break;
        ans = quit(a, b);
        printf("%d
", ans);
    }
    return 0;
}

普通求幂算法的时间复杂度为O(n)，当我们想求2的1000000000的最后3位数时需要的时间会很长

什么是快速幂算法

快速幂算法的核心思想时讲指数减少而将底数增大从而减少循环次数 我们来看一个栗子

2 ^ 9 = 28 * 2 //此时底数为2 =44 * 2//此时底数为4 =162 * 2//此时底数为16 =2561 * 2//此时底数为256 可以看出 29 结果等于所有指数为奇数时的底数的乘积

下面我们用代码演示！

long long fastPower(long long base, long long power)
{
          
   
    long long ans = 1;
    while(power > 0)
    {
          
   
        if(power % 2 == 0)//如果指数为偶数
        {
          
   
            power /= 2;//把指数缩小一半
            base = base * base % 1000;//底数平方
        }
        else
        {
          
   
            power--;//指数减一
            power /= 2;//把指数缩小一半
            ans *= base % 1000;//指数为奇数时的积
            base = base * base % 1000;//底数平方
        }
    }
    return ans;
}

快速幂算法的优化

long long fastPower(long long base, long long power)
{
          
   
    long long ans = 1;
    while(power > 0)
    {
          
   
        if(power % 2 == 1)
        {
          
   
            ans *= base % 1000;
        }
        power /= 2;
        base *= base % 1000;
    }
    return ans;
}

最终优化

我们可以将power % 2 == 1 用更快的 power&1来代替，这种运算被称为“位运算”，power&1，在二进制中如果最后一位为1，那么该数为奇数，如果最后一位为0，那么最后一位为偶数，此时与1进行&运算，若为奇数，则结果为1，若为偶数则结果为0‘ 于是代码为

long long fastPower(long long base, long long power)
{
          
   
    long long ans = 1;
    while(power > 0)
    {
          
   
        if(power&1)
        {
          
   
            ans *= base % 1000;
        }
        power /= 2;
        base *= base % 1000;
    }
    return ans;
}