快速幂

快速幂

快速计算某个数的多少次幂，时间复杂度O(logn)
own 理解：通过把十进制幂不断除以2变为2进制位（划分幂，使得幂划分部分减少），比如(11)10=(1011)2，这样可以把高次幂的计算时间复杂度由O(n)降为O(logn)。然后由

这里用了一个很强大的技巧,y*y即求出了a^(2^(i-1))
a^(2^(i-1))*a^(2^(i-1))=a^(2^i)
而且一般情况下a*b mod c =(a mod c)*(b mod c) mod c

可以知道，通过比本位低一位的权相乘可以得到本位的权，即2^0,2^1,2^2，……，2^n，之后就要判断幂是否能划分成该位的权。可以通过二进制的最低位来判断，现在每一位都对应一个权，在不断右移二进制位时，如果该位为0即表明幂的划分中没有该位的权，如果为1，则在最后的答案上乘上该位的权，直到二进制数为0.在规定了模值的情况下，应该知道，相乘的过程是可能会溢出的，所以要根据乘数的范围，定义一个恰当的类型（一般，long long int），而且赋值也可能会溢出，所以最后取模。
不是

int n = a * a;
n = n % 1000;

而应该是

int n = a * a % 1000;

（一）快速幂位操作

#include <iostream>
#include <cstdio>
using namespace std;
//位操作
const int MOD = 100000;
long long int pow4(long long int a,long long int b)
{
    long long int r = 1;
    long long int base;
    base = a % MOD;
    while(b != 0)
    {
        if(b & 1) r = (r * base) % MOD;
        base = (base * base) % MOD;
        //printf("base = %lld\n",base);
        b >>= 1;
    }
    return r;
}
int main()
{
    long long int a,b;
    while(scanf("%lld%lld",&a,&b) != EOF)
    {
        printf("%lld的%lld次幂为%lld\n",a,b,pow4(a,b));
    }
    return 0;
}

（二）快速幂

#include <iostream>
#include <cstdio>
using namespace std;
//位操作
const int MOD = 10000000;
long long int PowerMod(long long int a,long long int b)
{
    long long int ans = 1;
    a = a % MOD;
    while(b > 0)
    {
        if(b % 2 == 1) ans = (ans * a) % MOD;
        a = (a * a) % MOD;
        b = b / 2;
        //printf("a = %lld\n",a);
    }
    return ans;
}
int main()
{
    long long int a,b;
    while(scanf("%lld%lld",&a,&b) != EOF)
    {
        printf("%lld的%lld次幂为%lld\n",a,b,PowerMod(a,b));
    }
    return 0;
}

百度

博客