피보나치 수와 최대공약수

• 두가지만 알고 있으면 된다.
  • 피보나치 수의 최대공약수에 관한 수식 gcd(f[i],f[j]) = f[gcd(i,j)]
  • n번째 피보나치 수 (Fibonacci numbers)를 O(logn)에 구하는 방법
• 이제 그대로 구현하면 된다. n과 m의 최대공약수 p를 구하고, p번째 피보나치수를 구한다. 둘다 O(logn)에 처리된다

"""Solution code for "BOJ 11778. 피보나치 수와 최대공약수".

- Problem link: https://www.acmicpc.net/problem/11778
- Solution link: http://www.teferi.net/ps/problems/boj/11778
"""

import math
from teflib import combinatorics

MOD = 1_000_000_007


def main():
    n, m = [int(x) for x in input().split()]
    print(combinatorics.fibonacci(math.gcd(n, m), MOD))


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.fibonacci