시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 70 30 25 40.323%

문제

소수 P(2 ≤ P < 231), 정수 B(2 ≤ B < P), 정수 N(1 ≤ 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을 이용해야 한다. (링크

W3sicHJvYmxlbV9pZCI6IjQzNTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWMwYjAgXHViODVjXHVhZGY4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxOGNcdWMyMTggUCgyICZsZTsgUCAmbHQ7IDI8c3VwPjMxPFwvc3VwPiksIFx1YzgxNVx1YzIxOCBCKDIgJmxlOyBCICZsdDsgUCksIFx1YzgxNVx1YzIxOCBOKDEmbmJzcDsmbGU7IE4gJmx0OyBQKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJjMTFcdWM3NDQgQiwgXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFBcdWI4NWMgXHVkNTU4XHViMjk0IE5cdWM3NTggXHVjNzc0XHVjMGIwIFx1Yjg1Y1x1YWRmOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjOTg5LCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjODE1XHVjMjE4IExcdWM3NDQgXHVjYzNlXHVjNzNjXHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+QjxzdXA+TDxcL3N1cD4gPT0gTiAobW9kIFApPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgUCwgQiwgTlx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIE5cdWM3NTggXHVjNzc0XHVjMGIwIFx1Yjg1Y1x1YWRmOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IExcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzFjXHViNzdjXHViYTc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWFkZjhcdWI3ZWNcdWQ1NWMgTFx1Yzc3NCBcdWM1YzZcdWM3NDQgXHViNTRjXHViMjk0ICZxdW90O25vIHNvbHV0aW9uJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTIwIEFDTS1JQ1BDXHViMzAwXHVkNjhjXHVjNWQwXHVjMTFjIFx1Yzc5OCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IEZlcm1hdCYjMzk7cyBsaXR0bGUgdGhlb3JlbVx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiAoPGEgaHJlZj1cImh0dHA6XC9cL2VuLndpa2lwZWRpYS5vcmdcL3dpa2lcL0Zlcm1hdCdzX2xpdHRsZV90aGVvcmVtXCI+XHViOWMxXHVkMDZjPFwvYT4pJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MzU3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGlzY3JldGUgTG9nZ2luZyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBwcmltZSBQLCAyICZsdDs9IFAgJmx0OyAyPHN1cD4zMTxcL3N1cD4sIGFuIGludGVnZXIgQiwgMiAmbHQ7PSBCICZsdDsgUCwgYW5kIGFuIGludGVnZXIgTiwgMSZuYnNwOyZsdDs9IE4gJmx0OyBQLCBjb21wdXRlIHRoZSBkaXNjcmV0ZSBsb2dhcml0aG0gb2YgTiwgYmFzZSBCLCBtb2R1bG8gUC4gVGhhdCBpcywgZmluZCBhbiBpbnRlZ2VyIEwgc3VjaCB0aGF0PFwvcD5cclxuXHJcbjxwPkI8c3VwPkw8XC9zdXA+ID09IE4gKG1vZCBQKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+UmVhZCBzZXZlcmFsIGxpbmVzIG9mIGlucHV0LCBlYWNoIGNvbnRhaW5pbmcgUCxCLE4gc2VwYXJhdGVkIGJ5IGEgc3BhY2UsIGFuZCBmb3IgZWFjaCBsaW5lIHByaW50IHRoZSBsb2dhcml0aG0gb24gYSBzZXBhcmF0ZSBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIHRoZXJlIGFyZSBzZXZlcmFsLCBwcmludCB0aGUgc21hbGxlc3Q7IGlmIHRoZXJlIGlzIG5vbmUsIHByaW50ICZxdW90O25vIHNvbHV0aW9uJnF1b3Q7LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgc29sdXRpb24gdG8gdGhpcyBwcm9ibGVtIHJlcXVpcmVzIGEgd2VsbCBrbm93biByZXN1bHQgaW4gbnVtYmVyIHRoZW9yeSB0aGF0IGlzIHByb2JhYmx5IGV4cGVjdGVkIG9mIHlvdSBmb3IgUHV0bmFtIGJ1dCBub3QgQUNNIGNvbXBldGl0aW9ucy4gSXQgaXMgRmVybWF0JiMzOTtzIHRoZW9yZW0gdGhhdCBzdGF0ZXM8XC9wPlxyXG5cclxuPHA+QjxzdXA+KFAtMSk8XC9zdXA+ID09IDEgKG1vZCBQKTxcL3A+XHJcblxyXG48cD5mb3IgYW55IHByaW1lIFAgYW5kIHNvbWUgb3RoZXIgKGZhaXJseSByYXJlKSBudW1iZXJzIGtub3duIGFzIGJhc2UtQiBwc2V1ZG9wcmltZXMuIEEgcmFyZXIgc3Vic2V0IG9mIHRoZSBiYXNlLUIgcHNldWRvcHJpbWVzLCBrbm93biBhcyBDYXJtaWNoYWVsIG51bWJlcnMsIGFyZSBwc2V1ZG9wcmltZXMgZm9yIGV2ZXJ5IGJhc2UgYmV0d2VlbiAyIGFuZCBQLTEuIEEgY29yb2xsYXJ5IHRvIEZlcm1hdCYjMzk7cyB0aGVvcmVtIGlzIHRoYXQgZm9yIGFueSBtPFwvcD5cclxuXHJcbjxwPkI8c3VwPigtbSk8XC9zdXA+ID09IEI8c3VwPihQLTEtbSk8XC9zdXA+IChtb2QgUCkmbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Waterloo's local Programming Contests > 26 January, 2002 B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: chunghan