372. Super Pow

▶ 指数模运算。求 c 使得 c ≡ a^b (mod m)，其中 b 用 vector<int> 的形式保存（长整数），m = 1337

● 代码，18 ms，令 b=10c+d，则 a^b % m == ((a^c % m)¹⁰ % m) * (a^d % m) % m，递归，每次将指数的个位拆出来

 1 class Solution
 2 {
 3     const int mod = 1337;
 4     int powMod(int a, int k) //a^k mod 1337 where 0 <= k <= 10
 5     {
 6         a %= mod;
 7         int i, result;
 8         for (i = 0, result = 1; i < k; result = (result * a) % mod, i++);
 9         return result;
10     }
11 public:
12     int superPow(int a, vector<int>& b)
13     {
14         if (b.empty())
15             return 1;
16         int last_digit = b.back();
17         b.pop_back();
18         return powMod(superPow(a, b), 10) * powMod(a, last_digit) % mod;
19     }
20 };

● 代码，10 ms，与上面蕾丝是的算法，二进制优化了指数运算

 1 class Solution
 2 {
 3 public:
 4     const int mod = 1337;
 5     int powMod(int a, int b)// a ^ b % mod
 6     {
 7         int result;
 8         for (result = 1; b; b >>= 1)
 9         {
10             if (b & 1)
11                 result = (result * a) % mod;
12             a = (a * a) % mod;
13         }
14         return result;
15     }    
16     int superPow(int a, vector<int>& b)
17     {
18         int i, result;              
19         for (a %= mod, i = b.size() - 1, result = 1; i >= 0; i--)
20         {
21             if (i < b.size() - 1)
22                 a = powMod(a, 10);
23             result = (result * powMod(a, b[i])) % mod;
24         }
25         return result;
26     }
27 };

● 代码，8 ms，使用欧拉函数，注意到 a^b % m == a^{b % φ(m)} % m，φ(1337)=1140

 1 class Solution
 2 {
 3 public:
 4     const int mod = 1337;
 5     int superPow(int a, vector<int>& b)
 6     {
 7         int p = 0, ret;
 8         for (int i : b)
 9             p = (p * 10 + i) % 1140;
10         if (p == 0)
11             p += 1140;
12         for (ret = 1, a %= mod; p > 0; a = a * a % mod, p >>= 1)
13         {
14             if (p & 1)
15                 ret = ret * a % mod;
16         }
17         return ret;
18     }
19 };