Understanding solution to the problem Exponentiation II from CSES problemset.

Правка en1, от gamsahabnida, 2020-09-17 21:27:46

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 ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский gamsahabnida 2020-09-17 21:29:07 40
en1 Английский gamsahabnida 2020-09-17 21:27:46 1091 Initial revision (published)