# C++ AC recursive solution

• The key observation is `pow(a,b)%1337` = `pow(1337*k+a,b) % 1337`

``````class Solution {
public:
long long myPow(long long num, int k) {
if (k == 0) return 1;
if (k == 1) return (num % 1337);
long long ret = myPow(num % 1337, k / 2) % 1337;
return (ret * ret * ((k%2) ? num : 1))%1337;
}

int superPow(int a, vector<int>& b) {
int L = b.size();
long long ret = 1;
for (int i = 0; i < L; i++) {
ret = (long long)(myPow(ret, 10) * (long long)myPow(a, b[i])) % 1337;
}
return ret;
}
};
```'``````

• Similar to yours. :-)

``````class Solution {
private:
int powMod(int x, int y) {
int result{1};
while (y > 0) {
if (y & 1) result = (result * x) % 1337;
y >>= 1;
x = (x * x) % 1337;
}
return result;
}
public:
int superPow(int a, vector<int>& b) {
a %= 1337;
int result = 1;
for (int i = 0; i < b.size(); i++) {
result = (powMod(result, 10) * powMod(a, b[i])) % 1337;
}
return result;
}
};
``````

• @serendip Your `myPow` is a weird mix of inefficient and complicated... you'd better either store `myPow(num % 1337, k / 2)` in a variable and use it twice, or recurse only once, to k-1.

• @StefanPochmann good points. Updated my solution

• @serendip A slight modification where avoid using long long.

``````class Solution {
public:
int superPow(int a, vector<int>& b) {
int res = 1;
for (int i = 0; i < b.size(); ++i) {
res = myPow(res, 10) * myPow(a, b[i]) % 1337;
}
return res;
}
private:
int myPow(int x, int n) {
if (n == 0) return 1;
x %= 1337;
int half = myPow(x, n/2);
if (n % 2 == 0) return half * half % 1337;
else return ((half * half) % 1337) * x % 1337;
}
};
``````

Similarly, we can use iterative version of myPow. I think the key is that three multiplication is easy to overflow, that's why long long type is required if we did not % 1337 immediately.

``````class Solution {
public:
int superPow(int a, vector<int>& b) {
int res = 1;
for (int i = 0; i < b.size(); ++i) {
res = myPow(res, 10) * myPow(a, b[i]) % 1337;
}
return res;
}
private:
int myPow(int x, int n) {
int res = 1;
x %= 1337;
while (n > 0) {
if (n & 1) res = res * x % 1337;
n >>= 1;
x = x * x % 1337;
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.