사용자 도구

사이트 도구


ps:problems:boj:11778

피보나치 수와 최대공약수

ps
링크https://www.acmicpc.net/problem/11778
출처BOJ
문제 번호11778
문제명피보나치 수와 최대공약수
레벨골드 1
분류

피보나치

시간복잡도O(logn)
인풋사이즈n <= 10^18
사용한 언어Python
제출기록32952KB / 72ms
최고기록56ms
해결날짜2022/04/28

풀이

코드

"""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()

토론

댓글을 입력하세요:
V C​ Q X​ O
 
ps/problems/boj/11778.txt · 마지막으로 수정됨: 2022/04/28 09:36 저자 teferi