# Help in CSES - Exponentiation II

Problem
Code:

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;

int power(long long a, int b)
{
long long res = 1;
if (!b) return res;
a %= mod;
if (!a) return 0;
while (b > 0)
{
if (b & 1) res = ((res*a)%mod);
b >>= 1;
a = ((a*a)%mod);
}
return res;
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
while (n--)
{
long long a, b, c;
cin >> a >> b >> c;
cout << power(a, power(b, c)) << '\n';
}
}



We have to find a^{b^c} \pmod{10^9+7}, \ 0 \leq a, \ b, \ c \leq 10^9 which I do in O(\log{b} + \log{c}) with modular exponentiation. For some reason, it shows WA.
For example,
case: 3 9 10
expected: 112070339
output: 967113723
Also, assume that 0^0 = 1.
I donâ€™t know what Iâ€™ve done wrong because it passes most cases.

1 Like

Well pow(a,pow(b,c))%mod != pow(a,pow(b,c)%mod)%mod.
Thatâ€™s why it gives WA.

5 Likes

Why 10^9+6? Shouldnâ€™t it be 10^9+7?

I guess this what he did and it is wrong.

1 Like

To evaluate a^{b^c}, we need to evaluate b^c first, right?
a^{b^c} \neq a^{bc}

pow(a,totient(mod)) == 1 (mod) // Fermatâ€™s theorem
Since mod here is prime
Therefore , pow(a,mod-1) == 1 (mod)
So basically taking pow(b,c)%(mod-1) will eliminate all 1â€™s.
And suppose x = pow(b,c)%(mod-1)

2 Likes

Firstly, you need to calculate a^{(b^c)} \mod p. You can calculate x = b^c \mod \phi(p), and then calculate a^x \mod p. This is because we know a^{\phi(p)} \equiv 1 \mod p if \gcd(a,p) = 1.

Also itâ€™s not O(\log b \log c) itâ€™s O(\log b + \log c)

3 Likes

Thanks a lot @say_ch_ee_zz, @everule1, @zeki and @akshitm16!

3 Likes

Oops, thatâ€™s a typo.

Did you read his code? This is not what he did in the codeâ€¦

1 Like

This is what I meant to say originally.

1 Like

@therealnishuz

You can refer here : https://www.geeksforgeeks.org/find-power-power-mod-prime/

My_solution

4 Likes