Hello World

백준 2749 : 피보나치 수 3 문제 링크 www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 내용 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다. n이 주어질때, n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다. Idea 이 문제를 시간초과 없이 풀기 위해서는 피사노 주기를 알아야한다. 피사노 주기란 피보나치 수를 m으로 나눈 나머지가 주기를 이룬다는 것이다. 즉, 일정한 패턴이 존재한다는 뜻이다. 피사노 주기..

백준 9471 : 피사노 주기 문제 링크 www.acmicpc.net/problem/9471 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. (2 ≤ M ≤ 1,000,000) www.acmicpc.net 문제 내용 1960년, IBM의 직원 Donald Wall은 피보나치수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다. 예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다. 나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10 임을 알 수 ..