CSES Exponentiation II

Problem : Find the value of $(a^{b^c})mod(10^9+7)$ where $1\le n\le 10^5$ and $1\le a,b,c \le 10^9$

In order to solve this problem, we need to understand the Fermat's little theorem:

$(a^p\equiv a) mod(p)$ Where p is a prime number.

If a is not divisible by p we can express as $$(a^{(p-1)}\equiv 1) mod(p)=1....(A)$$

Since $10^9+7 = prime = p$, I can rewrite $(a^{b^c})mod(10^9+7)$ into  $(a^{b^c})mod(p).....(B)$

Then, reform equation $(B)$ with equation $(A)$:

$(a^{b^c})mod(p)= (a^{d(p-1)+r})mod(p)$

Substitute equation $(A)$ with 1:

$ =1^{d}* (a^{r})mod(p) = (a^{r})mod(p)$where $b^c = d*(p-1)+r$, $r$ is remainder of $b^c$

Therefore, $(a^{b^c})mod(p) = (a^{(b^c)mod(p-1)})mod(p)$ where $p$ is a prime, $p = 10^9+7$

C++ Code Implementation:

#include <iostream>

using namespace std;
typedef unsigned long long int lld;
lld prime = 1e9+7;

lld my_pow(lld a, lld b, lld m)
{
    lld result = 1;
    lld intermediate = a;

    if(b==1) return a;

    while(b)
    {
        if(b&1)
        {
            result*=intermediate;
            result%=m;
        }
        intermediate*=intermediate;
        intermediate%=m;
        b>>=1;
    }

    return result;
}

int main()
{
    int n;
    cin>>n;

    for(int i=0;i<n;i++)
    {
        lld a,b,c;
        cin>>a>>b>>c;
        lld tmp = my_pow(b, c, prime-1);
        cout<<my_pow(a, tmp, prime)<<endl;
    }

    return 0;
}