$$ \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.

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

vreme memorija ulaz izlaz
0,1 s 64 Mb standardni izlaz standardni ulaz

Напиши програм који одређује колико има природних бројева \(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\).

Morate biti ulogovani kako biste poslali zadatak na evaluaciju.