시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10 5 5 55.556%

문제

소수 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"을 출력한다.

예제 입력 1

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

예제 출력 1

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

힌트

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

W3sicHJvYmxlbV9pZCI6IjQzNTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWMwYjAgXHViODVjXHVhZGY4IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMxOGNcdWMyMTggUCgyICZsZTsgUCAmbHQ7IDI8c3VwPjMxPFwvc3VwPiksIFx1YzgxNVx1YzIxOCBCKDIgJmxlOyBCICZsdDsgUCksIFx1YzgxNVx1YzIxOCBOKDIgJmxlOyBOICZsdDsgUClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYzExXHVjNzQ0IEIsIFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBQXHViODVjIFx1ZDU1OFx1YjI5NCBOXHVjNzU4IFx1Yzc3NFx1YzBiMCBcdWI4NWNcdWFkZjhcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzk4OSwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOCBMXHVjNzQ0IFx1Y2MzZVx1YzczY1x1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdEI8c3VwPkw8XC9zdXA+ID09IE4gKG1vZCBQKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFAsIEIsIE5cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBOXHVjNzU4IFx1Yzc3NFx1YzBiMCBcdWI4NWNcdWFkZjhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBMXHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMxY1x1Yjc3Y1x1YmE3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVhZGY4XHViN2VjXHVkNTVjIExcdWM3NzQgXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1YjI5NCAmcXVvdDtubyBzb2x1dGlvbiZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzEyMCBBQ00tSUNQQ1x1YjMwMFx1ZDY4Y1x1YzVkMFx1YzExYyBcdWM3OTggXHVjMGFjXHVjNmE5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBGZXJtYXQmIzM5O3MgbGl0dGxlIHRoZW9yZW1cdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gKDxhIGhyZWY9XCJodHRwOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9GZXJtYXQnc19saXR0bGVfdGhlb3JlbVwiPlx1YjljMVx1ZDA2YzxcL2E+KSZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDM1NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRpc2NyZXRlIExvZ2dpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgcHJpbWUgUCwgMiAmbHQ7PSBQICZsdDsgMjxzdXA+MzE8XC9zdXA+LCBhbiBpbnRlZ2VyIEIsIDIgJmx0Oz0gQiAmbHQ7IFAsIGFuZCBhbiBpbnRlZ2VyIE4sIDIgJmx0Oz0gTiAmbHQ7IFAsIGNvbXB1dGUgdGhlIGRpc2NyZXRlIGxvZ2FyaXRobSBvZiBOLCBiYXNlIEIsIG1vZHVsbyBQLiBUaGF0IGlzLCBmaW5kIGFuIGludGVnZXIgTCBzdWNoIHRoYXQ8XC9wPlxyXG5cclxuPHA+QjxzdXA+TDxcL3N1cD4gPT0gTiAobW9kIFApPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5SZWFkIHNldmVyYWwgbGluZXMgb2YgaW5wdXQsIGVhY2ggY29udGFpbmluZyBQLEIsTiBzZXBhcmF0ZWQgYnkgYSBzcGFjZSwgYW5kIGZvciBlYWNoIGxpbmUgcHJpbnQgdGhlIGxvZ2FyaXRobSBvbiBhIHNlcGFyYXRlIGxpbmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgdGhlcmUgYXJlIHNldmVyYWwsIHByaW50IHRoZSBzbWFsbGVzdDsgaWYgdGhlcmUgaXMgbm9uZSwgcHJpbnQgJnF1b3Q7bm8gc29sdXRpb24mcXVvdDsuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBzb2x1dGlvbiB0byB0aGlzIHByb2JsZW0gcmVxdWlyZXMgYSB3ZWxsIGtub3duIHJlc3VsdCBpbiBudW1iZXIgdGhlb3J5IHRoYXQgaXMgcHJvYmFibHkgZXhwZWN0ZWQgb2YgeW91IGZvciBQdXRuYW0gYnV0IG5vdCBBQ00gY29tcGV0aXRpb25zLiBJdCBpcyBGZXJtYXQmIzM5O3MgdGhlb3JlbSB0aGF0IHN0YXRlczxcL3A+XHJcblxyXG48cD5CPHN1cD4oUC0xKTxcL3N1cD4gPT0gMSAobW9kIFApPFwvcD5cclxuXHJcbjxwPmZvciBhbnkgcHJpbWUgUCBhbmQgc29tZSBvdGhlciAoZmFpcmx5IHJhcmUpIG51bWJlcnMga25vd24gYXMgYmFzZS1CIHBzZXVkb3ByaW1lcy4gQSByYXJlciBzdWJzZXQgb2YgdGhlIGJhc2UtQiBwc2V1ZG9wcmltZXMsIGtub3duIGFzIENhcm1pY2hhZWwgbnVtYmVycywgYXJlIHBzZXVkb3ByaW1lcyBmb3IgZXZlcnkgYmFzZSBiZXR3ZWVuIDIgYW5kIFAtMS4gQSBjb3JvbGxhcnkgdG8gRmVybWF0JiMzOTtzIHRoZW9yZW0gaXMgdGhhdCBmb3IgYW55IG08XC9wPlxyXG5cclxuPHA+QjxzdXA+KC1tKTxcL3N1cD4gPT0gQjxzdXA+KFAtMS1tKTxcL3N1cD4gKG1vZCBQKSZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d