백준 11778번 - 피보나치 수와 최대공약수https://www.acmicpc.net/problem/11778 문제n 번째 피보나치 수와 m 번째 피보나치 수의 최대공약수를 구해보자. 입력n과 mn과 m은 1,000,000,000,000,000,000보다 작거나 같은 자연수 출력n 번째 피보나치 수와 m 번째 피보나치 수의 최대공약수를 1,000,000,007으로 나눈 나머지 접근최대공약수는 유클리드 호제법으로 구한다.GCD(a, b) = GCD(b, a % b)피보나치 수는 수가 매우 크기 때문에 DP로 구하면 시간초과행렬 곱셈을 활용하여 O(log N)의 시간복잡도로 피보나치 수를 구해야한다.C++ Code#include #include #include #include using namespace ..