ps:problems:boj:11778
목차
피보나치 수와 최대공약수
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 11778 |
| 문제명 | 피보나치 수와 최대공약수 |
| 레벨 | 골드 1 |
| 분류 |
피보나치 |
| 시간복잡도 | O(logn) |
| 인풋사이즈 | n <= 10^18 |
| 사용한 언어 | Python |
| 제출기록 | 32952KB / 72ms |
| 최고기록 | 56ms |
| 해결날짜 | 2022/04/28 |
풀이
- 두가지만 알고 있으면 된다.
- 피보나치 수의 최대공약수에 관한 수식 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
ps/problems/boj/11778.txt · 마지막으로 수정됨: 2022/04/28 09:36 저자 teferi
토론