You are viewing a single comment's thread. Return to all comments →
MOD = 10 ** 9 + 7
from math import gcd from functools import lru_cache
@lru_cache(None) def F(n): if n in [1,2]: return 1 if n == 3: return 2 M = n//2 N = M+n%2 return (F(M-1)*F(N) + F(M)*F(N+1))%MOD
n = int(input()) g = int(input()) for _ in range(n-1): g = gcd(g,int(input())) print(F(g))
Seems like cookies are disabled on this browser, please enable them to open this website
Fibonacci GCD
You are viewing a single comment's thread. Return to all comments →
F(m+n) = F(m-1)*F(n) + F(m)*F(n+1)
MOD = 10 ** 9 + 7
from math import gcd from functools import lru_cache
@lru_cache(None) def F(n): if n in [1,2]: return 1 if n == 3: return 2 M = n//2 N = M+n%2 return (F(M-1)*F(N) + F(M)*F(N+1))%MOD
n = int(input()) g = int(input()) for _ in range(n-1): g = gcd(g,int(input())) print(F(g))