快速幂(取模)算法

问题

计算取模运算的值 $ a^n \% b$,其中a、b、n均为int类型的变量。

分析

因为 $a^n$ 可能很大,所以不能先计算 $a^n$ 再将其 $ \%b$ 。

现有取模公式,写作:

$ (a*b) \% c = [ (a \% c) \times (b \% c) ] \% c $

那么:

  • 幂为偶数,则有 $ a^n \% b = (a^{\frac n 2} \times a^{\frac n 2}) \% b = [(a^{\frac n 2} \% b) \times (a^{\frac n 2}) \% b ] \% b​$
  • 幂为奇数,则有 $ (a \times a^{n-1}) \% b = [(a \% b) \times (a^{n-1} \% b)] \%b $,其中 $ a^{n-1} \% b$ 对应到幂为偶数的情况

代码

递归

递归写法(会溢出)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fastPower(int a, int b, int n) {
if (n == 0) {
return 1 % b;
} else if (n == 1) {
return a % b;
}

if (n % 2 == 1) {
return ((a % b) * fastPower(a, b, n - 1)) % b;
} else {
int res = fastPower(a, b, n / 2);
return (res * res) % b;
}
}

溢出点:

  • 奇数幂时,在计算 res * res 时可能超出int范围。
  • 偶数幂时,在计算(a % b) * fastPower(a, b, n - 1) 时可能超出范围

改正后:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fastPower(int a, int b, int n) {
if (n == 0) {
return 1 % b;
} else if (n == 1) {
return a % b;
}

if (n % 2 == 1) {
return ((a % b) * (long long)fastPower(a, b, n - 1)) % b;
} else {
long long res = fastPower(a, b, n / 2) % b;
return (res * res) % b;
}
}

迭代

所有的递归函数都能写成迭代的形式。

1
2
3
4
5
6
7
8
9
int fastPower(int a, int b, int n) {
long long r = 1, aa=a;
while(n) {
if (n & 1 == 1) r = (r * aa) % b;
n >>= 1;
aa = (aa * aa) % b;
}
return r % b;
}
坚持原创文章分享,您的支持将鼓励我继续创作!