# Share my C++ solution with a brief explanation, easy to understand

• a ^ b = a ^ (b1 * 10 + c)
= (a ^ c) * (a ^ (10 * b1))
= (a ^ c) * ((a ^ 10) ^ b1)

c = 2 ^ x1 + 2 ^ x2 +...... 2 ^ xn, xi = 0 or 1
a ^ c = (a * a)^x1 * (a * a)^x2 * ...... * (a * a)^xn

``````class Solution {
public:
const int MOD = 1337;

int superPow(int a, vector<int>& b) {
int n = b.size();
int ret = 1;

for (int i = n-1; i >= 0; i--)
{
ret = ret * pow_help(a, b[i]) % MOD;
a = pow_help(a, 10);
}

return ret;
}

int pow_help(int a, int b)
{
int ret = 1;
a %= MOD;

while (b > 0)
{
if (b & 1)
ret = ret * a % MOD;

b >>= 1;
a = a * a % MOD;
}

return ret;
}
};
``````

• another approach, but time limit exceeded

``````    int superPow(int a, vector<int>& b) {
int n = b.size();
const int MOD = 1337;
int ret = 1;
bool is_odd = false;

if (is_zero(b))
return 1;

a = a % MOD;

if (b[n-1] % 2 == 1)
is_odd = true;

divide_two(b);
ret = superPow(a, b) % MOD;
ret = (ret * ret) % MOD;

if (is_odd)
ret = (ret * a) % MOD;

return ret;
}

void divide_two(vector<int> &b)
{
int n = b.size();
int remainder = 0;

for (int i = 0; i < n; i++)
{
b[i] += 10 * remainder;
remainder = b[i] % 2;
b[i] /= 2;
}
}

bool is_zero(vector<int> &b)
{
int n = b.size();

for (int i = 0; i < n; i++)
{
if (b[i] > 0)
return false;
}

return true;
}
``````

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