백준 11440번: 피보나치 수의 제곱의 합
www.acmicpc.net/problem/11440 11440번: 피보나치 수의 제곱의 합 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제 역시 이전의 세 글과 같이 특정 성질을 이용하여 푸는 문제이지만, 그 성질이 비교적 유도가 힘든 것 같습니다. (백준 11443번: 짝수번째 피보나치 수의 합 , 백준 11442번: 홀수번째 피보나치 수의 합 , 백준 2086번: 피보나치 수의 합) 때문에 다른 성질들과는 다르게 이번엔 유도과정을 조금 보여드리려 합니다. $ F_{i}^{2}=F_{i}\times F_{i}=F_{i}\times \left ( F_{i+1}-F_{i-1} \right ) $ 이므로, $ ..
백준 11238번: Fibo
www.acmicpc.net/problem/11238 11238번: Fibo Fibonacci sequence is a well-known integer sequence that has many beautiful properties. Fibonacci sequence is something looks like this 0, 1, 1, 2, 3, 5, 8, 13, 21, … To make it formal, the mathematical term of Fibonacci sequence is define by recurrence www.acmicpc.net 슬슬 지겨워지는 피보나치 수입니다. 본문에서는 피보나치 수를 재귀적으로 구하는 방법, 일반화된 피보나치 수 공식에, 추가적으로 성질 두 가지를 소개하고 ..
백준 11778번: 피보나치 수와 최대공약수
www.acmicpc.net/problem/11778 11778번: 피보나치 수와 최대공약수 첫째 줄에 n과 m이 주어진다. n과 m은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이제 피보나치 수 자체만을 구하는 게 아니고 조금씩 변형이 되고 있습니다. 이 문제에서는 다음과 같은 성질을 알고 있어야 합니다. $ GCD \left ( F_{a}, F_{b}\right ) = F_{GCD \left ( a, b \right )} $ 최대공약수, GCD를 구하는 방법은 유클리드 호제법을 이용하면 충분합니다. long long GCD (long long x, long long y) { long long temp; while (y > 0) { temp ..
백준 2749번: 피보나치 수 3
www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 전에 올렸던 피보나치 수 6, Immortal Porpoises와 거의 동일한 문제입니다. ( 백준 11524번: Immortal Porpoises , 백준 11444번: 피보나치 수 6 ) 차이점으로는 modulo 값이 $ 10^{6} $ 으로 상당히 작다는 점입니다. 따라서 피사노 주기가 $ 15\times 10^{5} $ 이므로 이를 활용하여 코드를 짤 수 있습니다. (피사노 주기란, 피보나치 수의 mod 값의 주기를 말합니다.) 먼저 정석적으로, $ O \left ( logN \rig..