17840번 - 피보나치 음악 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 1596 | 341 | 232 | 19.728% |
문제
작곡가 철수는 피보나치 수열을 이용하여 만든 피아노 곡을 우연히 유튜브에서 보게 되었다. 피보나치 수열이란 f1 = 1, f2 = 1, fn+2 = fn+1 + fn (모든 n ≥ 1에 대해)을 만족하는 수열이다.
이 곡은 피보나치 수열의 각 자리 숫자에 해당하는 건반을 눌러서 만들어졌다. 피보나치 수열의 첫 8개 항을 사용해 곡을 만든다면, 다음과 같이 건반을 총 10번 누르게 될 것이다.
1 → 1 → 2 → 3 → 5 → 8 → 1 → 3 → 2 → 1
철수는 자신도 이 방법을 사용해 보기로 마음먹었다. 그런데 피보나치 수열은 너무 빠르게 증가해서, 덧셈에 약한 철수가 계산하기에는 어려웠다.
그래서 철수는 방법을 조금 바꾸기로 했다. 철수는 어떤 수 M을 정한 후, 피보나치 수열의 각 항을 M으로 나눈 나머지를 구하고, 각 수의 각 자리 숫자로 새로운 수열 을 만들어 이에 따라 피아노 곡을 쓰려고 한다.
예를 들어 M=10일 때, 새로운 수열 은 다음과 같다.
{1, 1, 2, 3, 5, 8, 3, 1, …}
따라서 철수는 1 →1 → 2 → 3 → 5 → 8 → 3 → 1 → 4 → … 순으로 건반을 누르게 된다.
이때, 철수는 어떤 N에 대해 N번째로 누르게 되는 건반의 번호(i.e. 새로운 수열 의 N번째 항)가 궁금해졌다.
Q개의 N이 질의로 주어졌을 때, 각각의 질의에 대해 N번째로 누르게 되는 건반의 번호를 출력하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 정수 Q와 M이 공백을 사이에 두고 주어진다.
두 번째 줄부터 Q개의 줄에 각각의 질의를 나타내는 정수 N이 주어진다.
출력
각각의 N에 대해, N번째로 누르게 되는 건반의 번호(새로운 수열의 N 번째 항)를 입력에 주어진 순서대로 총 Q개의 줄에 출력한다.
제한
- 1 ≤ N ≤ 1015
- 2 ≤ M ≤ 1,000
- 1 ≤ Q ≤ 100,000
예제 입력 1
2 10 5 8
예제 출력 1
5 1
출처
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호