Jump to content
aurelL

fractii help

Recommended Posts

Gigel, intr-o zi cand isi facea temele la matematica, s-a apucat sa scrie pe o foaie de hartie, un sir de fractii ireductibile de forma P/Q cu 1 ≤ P,Q ≤ N, unde N este un numar natural ales de el. De exemplu, pentru N = 4 el a obtinut urmatorul sir:

1/11/21/31/42/12/33/13/23/44/14/3

Gigel s-a apucat apoi sa numere cate fractii a obtinut pentru N = 4 si a vazut ca sunt 11.

Cerinta

Fiind dat un numar natural N, sa se determine cate fractii sunt in sirul de fractii construit dupa regulile de mai sus.

Date de intrare

Fisierul de intrare fractii.in contine pe prima linie numarul natural N.

Date de iesire

Fisierul de iesire fractii.out trebuie sa contina un numar natural pe prima linie care reprezinta cate fractii sunt in sir.

Restrictii si precizari

  • 1 ≤ N ≤ 1.000.000

 

 Am luat-o de pe un site. Inainte sa caut probleme mi-am propus sa le rezolv in O(n) si sa fac grafic. ( ca sa exersez big O notation si calculul timpilor de executie ).

 Aici e un desen si o explicatie. Stiu ca m-am complicat, sunt praf. Altfel nu stiu sa o rezolv. : https://prnt.sc/m5g3eg

 Codul meu : ( C++ )

    #include <iostream>
     
    using namespace std;
     
    int main()
    {
        int N, P, P_copy, total, n; // n e numarul de cautari.
        cin >> N;
        n = 0;
        total = ((N-1)*N)/2;
        for ( P = 2; P <= N/2; ++P ) {
            for ( P_copy = 2; P_copy <= N; P_copy += P_copy )
            ++n;
            ++P;
            P_copy = P;
        }
        total = (total - n)*2+1;
        cout << total;
        return 0;
    }
     

 

  • Upvote 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...