Zhao70's Blog

快速幂取模

发表于 | 分类于

快速幂

基本公式

quickMod

过程

以 b 为偶数举例
a^b%c = ((a^2)^b/2)%c

若 b / 2仍为偶数， 那么
((a^2)^b/2)%c = (((a^2)^2)^(b/2)/2)%c

举例

1
2
3
4
5
3 ^ 16
= (3     * 3    ) ^ 8
= (3 ^ 2 * 3 ^ 2) ^ 4 //3^2 由上一步3 * 3得
= (3 ^ 4 * 3 ^ 4) ^ 2 //3^4 由上一步3 ^ 2 * 3 ^ 2得
= (3 ^ 8 * 3 ^ 8) ^ 1 //3^8 由上一步3 ^ 4 * 3 ^ 4得

代码

1
2
3
4
5
6
7
8
9
10
11
12
int myQuickPow1(int a, int b)
{
    int ans = 1;
    while(b != 0)
    {
        if(b % 2 == 1)
            ans = ans * a;
        a = a * a;
        b = b / 2;
    }
    return ans;
}

也可以取模

1
2
3
4
5
6
7
8
9
10
11
12
int myQuickMod1(int a, int b, int c)
{
    int ans = 1;
    while(b != 0)
    {
        if(b % 2 == 1)
            ans = (ans * a) % c;
        a = (a * a) % c;
        b = b / 2;
    }
    return ans;
}

参考链接

快速幂取余算法总结详解