Challenge문제는 필수가 아니기 때문에 못풀어도 괜찮습니다
fibo(a)와 fibo(b)를 직접 계산하면 unsigned long long으로 해도 overflow가 발생합니다 다른 방법을 찾아보세요
힌트를 드리자면 gcd(a,b)=gcd(a-b,b)입니다. 귀납법으로 간단하게 유추할 수 있으니 증명은 생략할게요
위의 공식으로 13과 8의 최대공약수를 구해보면
gcd(13,8)=gcd(5,8)=gcd(5,3)=gcd(2,3)=gcd(2,1)=gcd(1,1)=1
어디서 많이 본 숫자들이 나오지 않나요? ㅎㅎ
