시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 2 2 66.667%

문제

소수 P(2 ≤ P < 231), 정수 B(2 ≤ B < P), 정수 N(2 ≤ N < P)가 주어졌을 때, 밑을 B, 나머지를 P로 하는 N의 이산 로그를 구하는 프로그램을 작성하시오.

즉, 다음과 같은 조건을 만족하는 정수 L을 찾으면 된다.

BL == N (mod P)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 한 줄로 되어져 있고, P, B, N이 공백으로 구분되어져 있다.

출력

각각의 테스트 케이스에 대해서, N의 이산 로그를 출력한다. 만약, 해당하는 L이 여러개라면 가장 작은 값을 출력한다. 또, 그러한 L이 없을 때는 "no solution"을 출력한다.

예제 입력

5 2 1
5 2 2
5 2 3
5 2 4
5 3 1
5 3 2
5 3 3
5 3 4
5 4 1
5 4 2
5 4 3
5 4 4
12345701 2 1111111
1111111121 65537 1111111111

예제 출력

0
1
3
2
0
3
1
2
0
no solution
no solution
1
9584351
462803587

힌트

이 문제를 풀기 위해선 ACM-ICPC대회에서 잘 사용하지 않는 Fermat's little theorem을 이용해야 한다. (링크