Fractii

fractii

==Include(page="template/taskheader" task_id="fractii")==

== include(page="template/taskheader" task_id="fractii") ==
Poveste ...
h2. Cerinta

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:
 
p=. $^1^/{~1~}  ^1^/{~2~}  ^1^/{~3~}  ^1^/{~4~}  ^2^/{~1~}  ^2^/{~3~}  ^3^/{~1~}  ^3^/{~2~}  ^3^/{~4~}  ^4^/{~1~}  ^4^/{~3~}$
 
Gigel s-a apucat apoi sa numere cate fractii a obtinut pentru $N = 4$ si a vazut ca sunt $11$.

...

h2. Cerinta

h2. Restrictii

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

...

h2. Date de intrare

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

...

h2. Date de iesire

Fisierul de iesire $fractii.out$ trebuie sa contina un numar natural pe prima linie care reprezinta cate fractii sunt in sir.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 1.000.000$

...

h2. Exemple

h2. Exemplu

table(example). |_. fractii.in |_. fractii.out |
| 3 | 7 |
| 4 | 11 |
| 5 | 19 |
| 10| 63 |

| fractii.in | fractii.out |
| linia1
linia2
linia3
| linia1
linia2
|

==Include(page="template/taskfooter" task_id="fractii")==

== include(page="template/taskfooter" task_id="fractii") ==