$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem

Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Ојлерова функција

време меморија улаз излаз
0,1 s 64 Mb стандардни излаз стандардни улаз

Напиши програм који одређује колико има природних бројева \(m\) мањих или једнаких од датог броја \(n\) који су узајамно прости са \(n\) тј. за које је \(1 \leq m \leq n\) и \(nzd(m, n) = 1\).

Улаз

Са стандардног улаза уноси се број \(n\) (\(1 \leq n \leq 2\cdot 10^9\)).

Излаз

На стандардни излаз исписати само тражени број.

Пример

Улаз

9

Излаз

6

Објашњење

Бројеви узајамно прости са бројем \(n\) су бројеви 1, 2, 4, 5, 7 и 8 и има их укупно 6.

Пример 2

Улаз

1

Излаз

1

Објашњење

Број 1 задовољава услове \(1 \leq 1\) и \(nzd(1, 1) = 1\).

Морате бити улоговани како бисте послали задатак на евалуацију.

Претходни Следећи