4357번 - 이산 로그 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 397 | 208 | 128 | 45.390% |
문제
소수 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을 이용해야 한다. (링크)
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호