How to calculate (a ^ b) % c

general
21

Can you provide a link to the problem?

22

My friend! I have a question. If a and c arenā€™t coprime, it means that there is a prime (let it is pi) that a % pi == 0 && c % pi == 0, and pi is in the set of prime (we break c), and when we apply above formula, we canā€™t calculate value of ((a % pi) ^ (b % phi(pi))) % pi (because gcd(a, pi) > 1) (after calculate, we can use CRT to calculate the answer). Could you tell me more about that? Thank you in advance :smiley:

23

The language for above problem is Vietnamese, do you want to get the link?

24

I donā€™t know the question requiring, just understand that: "calculate a^b % c " :smiley:

25

if a % p = 0, then a^n % p will always be zero.

1 Like
26

Oh :D, thank you :smiley:

27

Donā€™t you think your if-else ladder for even exponent is very inefficient ?