A Math Contest P9 - Buy Some Get Some

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 512M

Problem type

Given integers a, n, p, find the smallest nonnegative integer x such that a^x \equiv n \pmod p.


1 < a, n, p < 2^{31}

p is a prime number.

Input Specification

The only line contains three space-separated integers, a, n, and p.

Output Specification

Output the smallest possible nonnegative integer x; if no such x exists, output DNE.

Sample Input 1

7 4 5

Sample Output 1


Sample Input 2

10 7 11

Sample Output 2



There are no comments at the moment.