[백준 11778] 피보나치 수와 최대공약수
11778번: 피보나치 수와 최대공약수첫째 줄에 n과 m이 주어진다. n과 m은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.www.acmicpc.net알고리즘 : 수학난이도 : 플래티넘Ⅴ 1. 문제요약1,000,000,000,000,000,000 이하의 두 자연수 n,m이 주어진다.n번째 피보나치 수와 m번째 피보나치 수의 최대공약수를 출력한다.다만 숫자가 너무 커지므로 1,000,000,007로 나눈 나머지를 출력한다.2. 아이디어$gcd(F_n,F_m)$을 구하는 문제인데, 이 문제를 풀려면 유클리드 호제법을 알고 있어야 한다.유클리드 호제법은 $gcd(x,y) = gcd(x-y,y)$을 의미하는데, 이를 일반화하면 $gcd(x,y) = gcd(y,z)$가 된다. (여기..
2024. 4. 11.
[백준 11444] 피보나치 수 6
11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 : 수학 난이도 : 골드Ⅱ 1. 문제요약 1,000,000,000,000,000,000 이하의 자연수 n이 주어질때, n번째 피보나치수를 출력하는 프로그램을 작성한다. 다만 숫자가 너무 커지므로 1,000,000,007로 나눈 나머지를 출력하도록 한다. 2. 아이디어 지금까지 피보나치수는 점화식으로 구해왔으나, 이번에 주어진 n의 범위가 매우 크기때문에 점화식으로 구할시 반드시 시간초과가 뜰 수 밖에 없다. 일단 $10^{18}$이라는 숫자 자체가 힌트가 된다. 여기서 시간복잡도가 O(log n)이 되어야 함을 알 수 있다. 사실 ..
2024. 4. 11.
