Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Ułamki nieskracalne (ulamki-nieskracalne) Memory limit: 32 MB Time limit: 0.50 s Młody Jasio nie umie skracać ułamków! Dlatego lubi tylko ułamki nieskracalne (np. $\frac{2}{3}$ lub $\frac{3}{8}$), nie lubi zaś ułamków skracalnych (np. $\frac{2}{4}$ lub $\frac{4}{8}$). Analizuje teraz wszystkie ułamki właściwe (o wartości pomiędzy 0 a 1, wyłączając końce przedziału) o mianowniku N. Ile jest spośród nich ułamków nieskracalnych? Napisz program, który: wczyta liczbę N, wyznaczy liczbę właściwych ułamków nieskracalnych o mianowniku N i wypisze wynik na standardowe wyjście. Wejście W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N (mianownik ułamka). Wyjście Twój program powinien wypisać jedną liczbę całkowitą – liczbę nieskracalnych ułamków właściwych o mianowniku N. Ograniczenia 1 ≤ N ≤ 109. Częściowa punktacja W testach wartych łącznie 40% maksymalnej punktacji: N ≤ 106. Przykład Input Output Explanation 10 4 Szukane ułamki nieskracalne to: $\frac{1}{10}$, $\frac{3}{10}$, $\frac{7}{10}$, $\frac{9}{10}$.

Input	Output	Explanation
`10`	`4`	Szukane ułamki nieskracalne to: $\frac{1}{10}$, $\frac{3}{10}$, $\frac{7}{10}$, $\frac{9}{10}$.