題目

https://leetcode.com/problems/super-pow/

這道題的贊踩比例，讓人覺得是個大坑…

題解

快速冪，看了答案：C++ Clean and Short Solution

One knowledge: ab % k = (a%k)(b%k)%k
Since the power here is an array, we’d better handle it digit by digit.

One observation:

a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k

Looks complicated? Let me put it other way:

Suppose f(a, b) calculates a^b % k; Then translate above formula to using f :

f(a,1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k;

Implementation of this idea:

class Solution {int base = 1337;public int superPow(int a, int[] b) {return superPow(a, b, b.length - 1);}public int superPow(int a, int[] b, int i) {if (i == -1) return 1;int lastDigit = b[i];return powMod(superPow(a, b, --i), 10) * powMod(a, lastDigit) % base;}public int powMod(int a, int k) { // a^k%1337 (0<=k<=10)a %= base;int result = 1;for (int i = 0; i < k; i++) {result = (result * a) % base;}return result;} }

總結

以上是生活随笔為你收集整理的leetcode 372. Super Pow | 372. 超级次方（快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。