Rezolvare completă PbInfo #3047 fibofrac

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 < 263

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.

Exemplul 2:

fibofrac.in

2019

fibofrac.out

1547722

Exemplul 3:

fibofrac.in

500000

fibofrac.out

94988288219

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema fibofrac:

// prof. Chesca Ciprian
// Complexitate O(nlog(n))


#include <fstream>
#define nmax 1000003

using namespace std;

int n,i,j;

long long T=0;
int fi[nmax];


ifstream f("fibofrac.in");
ofstream g("fibofrac.out");


int main()
{

f>>n;

// calculez fi(i)
for (i=1;i<=n;i++)
    fi[i] = i-1;

fi[1]=1;
for (i=2;i<=n;i++)
   for (j=i+i;j<=n;j+=i)
        fi[j] -= fi[i];

for(i=1;i<=n/2;i++)
     T+=2*fi[i];

for(i=n/2+1;i<=n;i++)
     T+=fi[i];

g<<T - (n-2) - 3<<"\n";

f.close();
g.close();

return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3047 fibofrac

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3047 fibofrac de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!