Hello there! It's my first time writing a blog here. In the following problem titled Exponentiation II from the CSES problemset, Problem I was given three integers a, b, c and had to calculate the value of (a^b)^c modulo 1000000007 for each test case. I would write the exponentiation function and it gave correct answers for the provided test cases but WA for overall test cases. My function is as follows:
ll exp(ll x,ll n){
if(n == 0) return 1;
if(n == 1) return x;
if(n%2 == 0) return exp((x*x)%mod,n/2);
if(n%2 == 1) return (x*exp((x*x)%mod,n/2))%mod;
}
I call it as follows: exp(a, exp(b, c))
. But for the following method and call it gave the write answers:
ll modpow(ll b, ll p, ll m)
{
ll r = 1;
while(p){
if(p & 1) r = r*b%m;
b = b*b%m;
p /= 2;
}
return r;
}
It's call is modpow(a, modpow(b, c, mod-1), mod)
. Why does it have to be mod-1 ?