RebecaBud: Pagină nouă: == Enunt == Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N. == Cerinţa == Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci. == Date de intrare == Fișierul de intrare fibofrac.in conține pe prima linie numărul N. == Date de ieșire == Fișierul de ieșire fibofrac.out va c...

2024-06-03T17:50:47Z

Pagină nouă: == Enunt == Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N. == Cerinţa == Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci. == Date de intrare == Fișierul de intrare fibofrac.in conține pe prima linie numărul N. == Date de ieșire == Fișierul de ieșire fibofrac.out va c...

New page

== Enunt ==
Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N.
== Cerinţa ==
Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci.
== Date de intrare ==
Fișierul de intrare fibofrac.in conține pe prima linie numărul N.
== Date de ieșire ==
Fișierul de ieșire fibofrac.out va conține pe prima linie numărul F, cu semnificația de mai sus.
== Restricţii şi precizări ==
* Pentru teste în valoare de 24 puncte, 0 < N < 80
* Pentru teste în valoare de 40 puncte, 0 < N < 1101
* Pentru teste în valoare de 56 puncte, 0 < N < 50001
* Pentru teste în valoare de 100 puncte, 0 < N < 1.000.000
* Două fracții ireductibile a / b și c / d sunt diferite dacă a ≠ c sau b ≠ d.
* 0 ≤ F < 2^63
== Exemplul 1 ==
; fibofrac.in

7
; fibofrac.out

14
== Explicație ==
N = 7; Primii 7 termeni ai șirului Fibonacci sunt: 1, 1, 2, 3, 5, 8, 13. Se pot forma 14 fracții diferite ireductibile subunitare: 1/2, 1/3, 1/5, 1/8, 1/13, 2/3, 2/5, 2/13, 3/5, 3/8, 3/13, 5/8, 5/13, 8/13.
<br>

== Exemplul 2 ==
; fibofrac.in

2019
; fibofrac.out

1547722
<br>

== Exemplul 3 ==
; fibofrac.in

500000
; fibofrac.out

94988288219

<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def gcd(a, b):
while b:
a, b = b, a % b
return a

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

count = 0
for i in range(n):
for j in range(i + 1, n):
if gcd(fib[i], fib[j]) == 1:
count += 1
return count

def main():
with open("fibofrac.in", "r") as f_in:
n = int(f_in.readline().strip())

result = count_fibonacci_fractions(n)

with open("fibofrac.out", "w") as f_out:
f_out.write(str(result))

if __name__ == "__main__":
main()

</syntaxhighlight>

3047 - Fibo Frac - Revision history