You are viewing a single comment's thread. Return to all comments →
Hints:
(1) Euler's theorem: if a and n are coprime positive integers, we have
a^phi(n) mod n = 1,
where phi() is Euler's totient function. Fermat's little theorem is a special case of this where n is prime.
(2) What if a and n are not coprime? Try this:
a mod n = (a/d mod n/d)*d,
where d=gcd(a,n) is the greatest common divisor of a and n.
These are the main ingredients of this problem. Watch out for boundary cases.
Seems like cookies are disabled on this browser, please enable them to open this website
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
Devu Vs Police
You are viewing a single comment's thread. Return to all comments →
Hints:
(1) Euler's theorem: if a and n are coprime positive integers, we have
where phi() is Euler's totient function. Fermat's little theorem is a special case of this where n is prime.
(2) What if a and n are not coprime? Try this:
where d=gcd(a,n) is the greatest common divisor of a and n.
These are the main ingredients of this problem. Watch out for boundary cases.