~/algor $ cat masalalar/sonlar-eyler-funksiyasi
Sonlar-05
Eyler funksiyasi
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
1000 ms
128 MB
66%
Natural son $n$ berilgan. $1$ dan $n$ gacha bo'lgan sonlar orasida $n$ bilan o'zaro tub bo'lganlari, ya'ni $\operatorname{EKUB}(k, n) = 1$ bo'lgan $k$ sonlar nechta ekanini toping. Bu son $\varphi(n)$ bilan belgilanadi; $\varphi(1) = 1$.
Kiruvchi ma'lumotlar
Bitta natural son $n$.
Chiquvchi ma'lumotlar
Bitta butun son — $\varphi(n)$.
Izoh
$1 \le n \le 10^{12}$
Misollar
Kirish #1
12
Chiqish #1
4
Kirish #2
9
Chiqish #2
6