시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1820 | 1281 | 1096 | 72.535% |
1960년, IBM의 직원 Donald Wall은 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다.
예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다.
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
F(n) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
F(n) mod 11 | 1 | 1 | 2 | 3 | 5 | 8 | 2 | 10 | 1 | 0 |
나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10임을 알 수 있다.
Wall은 아래와 같은 여러 가지 성질도 증명했다.
m이 주어졌을 때, k(m)을 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다.
각 테스트 케이스마다 테스트 케이스 번호를 출력하고 k(M)을 출력한다.
5 1 4 2 5 3 11 4 123456 5 987654
1 6 2 20 3 10 4 15456 5 332808
ICPC > Regionals > North America > Greater New York Region > 2013 Greater New York Programming Contest D번