www.acmicpc.net/problem/2086 2086번: 피보나치 수의 합 첫째 줄에 a와 b(1≤a≤b≤9,000,000,000,000,000,000)이 주어진다. www.acmicpc.net a번째 피보나치 수~b번째 피보나치 수의 합을 구하는 문제다. a부터 b까지 모든 피보나치 수의 합을 하나씩 구해서 더하면 O(N) 이므로 a가 1이고 b가 9e18 일 경우 무조건 시간 초과... 따라서 간단한 관찰을 통해 식을 구해야 한다. 1부터 10까지 전부 적어보면 1 2 3 4 5 6 7 8 9 10 1 1 2 3 5 8 13 21 34 55 인데 \(F_5\) 부터 \(F_7\) 까지 구해보면 합은 26이고 이는 \(F_9-F_6\) 인 것을 알 수 있다. 일반화해보면 $$F_{a \;to\;..

www.acmicpc.net/problem/11778 11778번: 피보나치 수와 최대공약수 첫째 줄에 n과 m이 주어진다. n과 m은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 문제들을 풀면서 비슷한 유형들 여러 가지를 푸는데 상당히 재미있다. 이번 문제는 행렬 제곱을 이용한 큰 수의 피보나치 수를 구해서 최대공약수를 구하는 것이다. 이 문제는 각각 n과 m에 대해서 피보나치 수열을 구하고 그 수의 최대 공약수를 구해도 되지만 n과 m을 미리 최대공약수를 구한 뒤 그 수의 피보나치 수를 구해도 된다. #include #include using namespace std; using ll = unsigned long long; const..

www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번에는 나누는 값이 1000000007이다. www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제에서는 나누는 값이 백만이라 피사노 주기를 통해서 구할 수 있었지만 이번 문제에서는 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. 조건 때문에 피사노 주기를 구하려면 시간 초과가 날 ..