Debug.Log

백준 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 ..

최대공약수, 최소공배수 알고리즘 유클리드 호제법으로 최대공약수 구하기최대공약수를 구하는 함수를 ​라고 하자.​ 이라면, ​ 임이 성립.​ 이 이라면, ​ 임이 성립한다.def gcd(a, b): mod = a%b while mod > 0: a = b b = mod mod = a%b return b 최소공배수최소공배수는 a과 b의 곱에 최대공약수를 나누어 준 것과 같다.def lcm(a, b): return a*b//gcd(a,b) 최대공약수 (GCD : Greatest Common Divisor)최소공배수 (LCM : Least Common Multiple)