CGPOWN EDITORIAL

PROBLEM LINK:

Practice

Setter - Bhanu Kiran Reddy

Editorial - Bhanu Kiran Reddy

DIFFICULTY :

Medium

PREREQUISITES :

modular exponentiation

and some basic math

PROBLEM :

For a given integers A, B and N you have to find ((AB) % N) - which is nothing but (A power B) modulus N. simple

EXPLANATION:

–>We can see the simple solution is to multiply a by b times

–>But it takes the complexity of O(b)

–>For efficient calculation of power see here. It takes the complexity of O(log(b))

–>Even though for large numbers we cannot store in long long so visit

SOLUTION :

Setter’s solution can be found here