2053 - Fibo Div

Enunt

Fie șirul Fibonacci, dat prin F[1] = 1, F[2] = 1 și relația de recurență F[k] = F[k-1] + F[k-2], k ≥ 3 . Se consideră un număr natural N și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T.

Cerinţa

Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1], A[2],...,A[N].

Date de intrare

Fișierul de intrare fibodiv.in conţine pe prima linie numerele N și T separate printr-un spațiu, iar pe a doua linie N numere naturale, A[1], A[2],...,A[N], separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire fibodiv.out va conţine pe prima linie numărul natural D,cu semnificația de mai sus.

Restricţii şi precizări

• 1 ≤ N ≤ 15
• 2 ≤ T ≤ 1018
• 2 ≤ A[i] ≤ 50, 1 ≤ i ≤ N

Exemplul 1

fibodiv.in

 3 20
 3 6 10

fibodiv.out

 6

Explicație

N = 3; T = 20; A1 = 3, A2 = 6, A3 = 10. Primii 20 de termeni ai șirului Fibonacci sunt: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765. Printre aceștia se găsesc 6 termeni divizibili cu cel puțin unul dintre numerele 3, 6, 10 și anume: 3, 21, 144, 610, 987, 6765.

Rezolvare

def fibonacci_sequence(n):
    fib = [1, 1]
    for i in range(2, n):
        fib.append(fib[i - 1] + fib[i - 2])
    return fib

def count_divisible_terms(fib_sequence, divisors):
    count = 0
    for term in fib_sequence:
        for divisor in divisors:
            if term % divisor == 0:
                count += 1
                break
    return count

def main():
    with open("fibodiv.in", "r") as fin:
        N, T = map(int, fin.readline().split())
        divisors = list(map(int, fin.readline().split()))

    fib_sequence = fibonacci_sequence(T)
    count = count_divisible_terms(fib_sequence, divisors)

    with open("fibodiv.out", "w") as fout:
        fout.write(str(count) + "\n")

if __name__ == "__main__":
    main()