372 Super Pow

题目

372 Super Pow

题解

题目要求计算 \(a^b \ mod \ 1337\)，其中b是由数组表示的大整数。根据模运算法则，有 \(ab \equiv [(a \ mod \ N) \times (b \ mod \ N)] (\ mod \ N)\) \(以 \times_N\) 表示相乘后模N，那么有 \(a^b \ mod \ 1337 = \underbrace{a \ mod \ 1337 \times_N a \ mod \ 1337 \times_N \dots \times_N a \ mod \ 1337 }_{b}\) 由于大整数b是以数组形式给出的，我们可以以这个形式 \(a \times 10^0 + b \times 10 ^1 + c \times 10^2 \dots\) 看待数组上的数字，也即是把\(a^b\)分解成一系列的幂。因此，算法可以从大整数b的最末位开始进行\(\times_N\)计算，每进位一次把当前位的模结果（一开始设为 \(m = a \ mod \ 1337\)）连续\(\times_N\) 10次

代码

#include <vector>

using namespace std;

class Solution {
public:
	int superPow(int a, vector<int>& b) {
		const int N = 1337;
		int result = 1;
		int mod = a % N;

		for (int i = b.size() - 1; i >= 0; --i) {
			if (b[i] > 0) {
				for (int count = 0; count < b[i]; ++count) {
					result = (result * mod) % N;
				}
			}
			int temp = 1;
			for (int j = 0; j < 10; ++j) {
				temp = (temp * mod) % N;
			}
			mod = temp;
		}
		return result;
	}
};