Given A, B and C. How to find the value of (A^B)%C.

I try many times but failed. input : A B C are 12345 123456789 123456789012345 repectively.
Output : 59212459031520
Please help me to solve this.

Use exponentiation by repeated squaring. This page on GeeksforGeeks explains this clearly enough. Hope this helps.

1 Like

Refer the below link:

Fast Modular Exponential

As suggested above the algorithm is mentioned above. But still there is a glitch here as the input you have mentioned contains a very large value of C. So the intermediate values will overflow and not fit even in “long long” or “unsigned long long”. There are no issues in python for this. But in C++, C, Java etc languages, this can be handles by using the trick given in this codeforces blog. It describes both O(1) and O(logn) solution for it. Thus the overall time complexity may vary, meaning O({\log}^{2} n) or O(\log n) depending on implementation using for avoiding overflow conditions.

3 Likes

In Java the BigInteger class is quite convenient for handling large numbers :slight_smile:

//