9371번 - 인코딩 좌표 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 128 MB | 90 | 32 | 24 | 36.923% |
문제
상근이는 테러리스트의 전화를 도청하던 중에 큰 공격이 예고되다는 사실을 알게되었다. 테러리스트는 인코딩된 좌표를 서로에게 보내고 있다. 상근이는 이 좌표 중 한 군데에서 공격이 일어날 것이라고 예상하고 있다. 상근이는 좌표를 가로채는데 성공했다.
모든 좌표는 x와 y 좌표로 나누어져 있으며, 두 좌표는 모두 소수 P보다 작은 음이 아닌 정수이다. x좌표와 y좌표는 각각 인코딩되며, 인코딩 되는 과정은 동일하다.
좌표 하나를 인코딩하려면 A, B, C, K, N이 필요하고, 다음과 같은 과정이 필요하다.
인코딩 과정은 세 함수로 나타낼 수 있고, 다음과 같다.
- F(n+1) = G(n) + H(n)
- G(n+1) = K*F(n) + H(n-1)
- H(n+1) = F(n) + K*G(n)
A, B, C는 함수의 초기값이다.
- F(1) = A
- G(1) = B
- H(1) = C
좌표는 F(N) mod P가 된다.
사실 위의 과정에는 매우 중요한 정보가 하나 빠져있다. G(2)를 계산하려면, H(0)이 필요하다. 하지만, H(0)을 알아낼 수 있는 방법은 없다. H(0)에 대한 유일한 정보는 x와 y를 계산할 때, 동일한 H(0)을 사용한다는 점이다.
상근이는 우연히 x좌표를 디코딩하지 않고 얻게 되었다. 이제, x를 이용해 H(0)을 구한 다음, y를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개보다 작거나 같다. 각 테스트 케이스의 첫째 줄에는 소수 P (2 ≤ P ≤ 19997)가 주어진다. 둘째 줄에는 x좌표를 인코딩하는데 사용하는 Ax, Bx, Cx, Kx, Nx가 주어진다. (0 ≤ Ax, Bx, Cx, Kx < P, 1 ≤ Nx ≤ 109) 셋째 줄에는 y좌표를 인코딩하는데 사용한 Ay, By, Cy, Ky, Ny가 주어진다. (0 ≤ Ay, By, Cy, Ky < P, 1 ≤ Ny ≤ 109) 넷째 줄에는 x좌표 (0 ≤ x < P)가 주어진다.
출력
각 테스트 케이스마다 y좌표를 출력한다. 만약, 가능한 y좌표가 여러 개인 경우에는 “UNKNOWN”를 출력한다.
예제 입력 1
2 11 2 3 5 7 4 4 6 8 9 7 5 7 1 6 2 5 1 3 4 2 5 3 1
예제 출력 1
7 UNKNOWN
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호