Super Pow问题及解法

本文主要是介绍Super Pow问题及解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

our task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

示例:

a = 2
b = [3]Result: 8

a = 2
b = [1,0]Result: 1024

问题分析：

利用欧拉准则和递归的方法，即可求得答案。

这里简单说一下欧拉准则：ab % k = (a%k)(b%k)%k

过程详见代码：

class Solution {
public:const int base = 1337;int powmod(int a, int k){a %= base;int res = 1;for (int i = 0; i < k; i++){res = (res * a) % base;}return res;}int superPow(int a, vector<int>& b) {if (b.empty()) return 1;int last = b.back();b.pop_back();return powmod(superPow(a, b), 10) * powmod(a, last) % base;}
};

这篇关于Super Pow问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---