leetcode 372. Super Pow | 372. 超级次方（快速幂）

缺乏、安全感 2022-08-29 13:50 216阅读 0赞

## 题目 ##

[https://leetcode.com/problems/super-pow/][https_leetcode.com_problems_super-pow]

这道题的赞踩比例，让人觉得是个大坑…  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

快速幂，看了答案：[C++ Clean and Short Solution][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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

[https_leetcode.com_problems_super-pow]: https://leetcode.com/problems/super-pow/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/77f2629471f24d4b8fd8530d1b30ad69.png
[C_ Clean and Short Solution]: https://leetcode.com/problems/super-pow/discuss/84472/C++-Clean-and-Short-Solution
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/3035539516ef4715ab24a21a33c04ff1.png