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.
Please help me.

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)
Then answer is simply pow(a,x)%mod

3 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 : Find power of power under mod of a prime - GeeksforGeeks

My_solution

4 Likes

If I want to calculate a^(b^(c^(d))) mod p and regarding ‘p’ I don’t know whether it is prime or not, then how to solve this problem.
Thanks in advance.