快速幂

快速幂的作用：快速计算底数的n次幂。
时间复杂度为：O(log₂N)　（朴素方法为O(N)

原理

以下以求a的b次方来介绍
把b转换成二进制数
该二进制数第i位的权为$2^{i-1}$
例：
　　$a^{11} = a^{2^0+2^1+2^3}$
11的二进制是1011
$11 = 2^3×1 + 2^2×0 + 2^1×1 + 2^0×1$
因此，我们将$a^{11}$转化为算$a^{2^0}×a^{2^1}×a^{2^3}$

代码

递归版

int powf(int a, int b){
    if(b == 1)
        return a;
    int t = powf(a, b/2);
    return (b%2 == 0 ? 1 : a)*t*t;
}

循环版

int pow0(int a, int b){
    int r = 1, base = a;
    while(b != 0){
        if(b%2)
            r *= base;
        base *= base;
        b /= 2;
    }
    return r;
}

//常规求幂
int pow1(int a, int b){
    int r = 1;
    while(b--)
        r *= a;
    return r;
}

//快速求幂（位运算）
int pow2(int a, int b){
    if(b == 0)
        return 1;
    else {
        while((b&1) == 0){
            b >>= 1;
            a *= a;
        }
    }
    int r = a;
    b >>= 1;
    while(b != 0){
        a *= a;
        if(b & 1)
            r *= a;
        b >>= 1;
    }
    return r;
}

//快速求幂（位运算，简洁版）
int pow3(int a, int b){
    int r = 1, base = a;
    while(b){
        if(b & 1)
            r *= base;
        base *= base;
        b >>= 1;
    }
    return r;
}

测试

#include <stdio.h>
//a^b
int powf(int a, int b){
    if(b == 1)
        return a;
    int t = powf(a, b/2);
    return (b%2 == 0 ? 1 : a)*t*t;
}
int pow0(int a, int b){
    int r = 1, base = a;
    while(b != 0){
        if(b%2)
        r *= base;
        base *= base;
        b /= 2;
    }
    return r;
}
//常规求幂
int pow1(int a, int b){
    int r = 1;
    while(b--)
        r *= a;
    return r;
}
//快速求幂（位运算）
int pow2(int a, int b){
    if(b == 0)
        return 1;
    else {
        while((b&1) == 0){
            b >>= 1;
            a *= a;
        }
    }
    int r = a;
    b >>= 1;
    while(b != 0){
        a *= a;
        if(b & 1)
            r *= a;
        b >>= 1;
    }
    return r;
}
//快速求幂（位运算，简洁版）
int pow3(int a, int b){
    int r = 1, base = a;
    while(b){
        if(b & 1)
            r *= base;
        base *= base;
        b >>= 1;
    }
    return r;
}

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("递归版：n");
    printf("%d^%d = %dnn", a, b, powf(a, b));
    printf("循环版：n");
    printf("%d^%d = %dnn", a, b, pow0(a, b));
    printf("常规求幂：n");
    printf("%d^%d = %dnn", a, b, pow1(a, b));
    printf("位运算1：n");
    printf("%d^%d = %dnn", a, b, pow2(a, b));
    printf("位运算2：n");
    printf("%d^%d = %dnn", a, b, pow3(a, b));
    return 0;
}

快速幂取余

首先要证明一个公式：a*b%m = $[($a%m$)*($b%m$)]$%m
$a = a_1*m+a_2$
$b = b_1*m+b_2$
a*b%m = $a_2*b_2$%m = $[($a%m$)*($b%m$)]$%m
进而
$a^b$%m = $[($a%m$)^b]$%m = $[($a%m$)*($a%m$)^{b-1}]$%m = { $($a%m$)*[($a%m$)^{b-1}$%m ] ] <script type="math/tex" id="MathJax-Element-78">]</script> }%m

代码

#include <stdio.h>
long long powMod(long long a, long long b, long long mod)
{
    long long ans = 1;
    a %= mod;
    while(b){
        if(b&1)
            ans = ans*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return ans;
}
int main(void)
{
    int a, b, mod;
    scanf("%d%d%d", &a, &b, &mod);
    printf("%d^%d%%%d = %lldnn", a, b, mod, powMod(a, b, mod));
    return 0;
}

最后

以上就是懦弱自行车为你收集整理的快速幂及其取余快速幂快速幂取余的全部内容，希望文章能够帮你解决快速幂及其取余快速幂快速幂取余所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。