[数据结构与算法]快速幂算法—迭代和递归

没学算法之前，我们求幂的方法 应该是简单的循环迭代，每次循环使得数乘以a。

int power(int a, int b) {
	int sum = 1;
	for (int j = 1; j <= b; j++) {
		sum *= a;
	}
	return sum;
}

这种方法简单，但时间复杂度为O(n)，如果我们所求的幂次过大，则难以在有限的时间里得到答案，如本题幂次的范围可达2^31，如果O(n)的复杂度去解决，也就是要花2^31/1e8秒..

所以基于此引出快速幂的算法。先以2^10（a^b)为例，我们可以得到这样的递推关系：

2^10=2^5 * 2^5

2^5=2 * 2^4

2^4=2^2 * 2^2

2^2=2^1 * 2^1

2^1=2 * 2^0

2^0=1

从这个关系可以看出，主问题2^10被逐步分解为两种子问题——幂次为奇，和幂次为偶，分别对这两种情况讨论即可：

1.幂次为偶数时，子问题化为求解，a^(b/2)。原问题的值则为a^(b/2)*a^(b/2)

2.幂次为奇数时，其子问题化为基数a*a^b-1。因为b为奇数，所以b-1为偶数，子问题转为求解偶数次幂a^b-1

根据这种关系，写出递归式就很简单了。

int  power(int  a, int  b) {
	if (b == 0)return 1;
	int ans = 0;
	if (b % 2 == 0) {
		ans = power(a, b / 2) * power(a, b / 2);
		return ans;
	}
	else
		return (a * power(a, b - 1));
}

这样已经可以得到答案了，但是这种递归会有个很大的问题，就是子问题大量重复计算。所以我们可以采用记忆化优化。其实就是开一个数组存放每个子问题的值，如果该子问题已经解决，则直接调用该值省去而外计算。

int rec[10000000];//存放该基数下每个幂次的值
int  power(int  a, int  b) {
	if (b == 0) {
		rec[0] = 1;
		return  1;
	}
	if (rec[b] != 0)return rec[b];
	else if (b % 2 == 0) {
		rec[b] = (power(a, b / 2) * power(a, b / 2));
		return rec[b];
	}
	else if (b % 2 == 1) {
		rec[b] = (a * power(a, b - 1) );
		return rec[b];
	}
}

但是对于这题，这样写又有一个问题，就是幂次过大，数组里每个元素都要存放对应的幂，数组开不了那么大。

所以采用迭代的方式会更方便。

所谓迭代就是每次循环更新操作完的值，对应求解幂来说就是更新基数。例如幂次10在一次操作后变为5，对应基数就变为a*a。

int  power(int  a, int  b) {
	int  ans = 1;//初始化ans，应对幂次为1和0的情况
		while (b) {
			if (b % 2 == 0) {
				b /= 2;
				a = a * a;
			}
			else {
				b -= 1;
				ans = ans * a ;
				b /= 2;
				a =a* a ;
			}
		}
		return ans;
}

?示例：

题目描述

给你三个整数 a,b,p，求 a^b mod p。

输入格式

输入只有一行三个整数，分别代表a,b,p。

输出格式

输出一行一个字符串 a^b mod p=s，其中 a,b,p 分别为题目给定的值， s 为运算结果。

输入输出样例

输入 #1

2 10 9

输出 #1

2^10 mod 9=7

说明/提示

样例解释

2^{10} = 1024，1024 mod 9 = 7。

数据规模与约定

对于 100% 的数据，保证0≤a,b<2^31，a+b>0。

作为快速幂的模板题，只需注意输出格式和取模即可（记得在运算前进行取模，防止运算后得数过大爆long long）

#include<iostream>
using namespace std;
//(a*b)%c=(a%c*b%c)%c;
long long  p;

long long   power(long long  a, long long  b) {
	int  ans = 1;//初始化ans，应对幂次为1和0的情况
		while (b) {
			if (b % 2 == 0) {
				b /= 2;
				a = a%p * a%p;
			}
			else {
				b -= 1;
				ans = ans * a%p ;
				b /= 2;
				a =a%p* a%p ;
			}
		}
		return ans;
}

int main() {
	long long  a, b;
	cin >> a >> b >>p;
	cout << a << "^" << b << " " << "mod" << " " << p << "=" << power(a, b);
}