Loading [MathJax]/jax/output/CommonHTML/jax.js

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

Problem sa prikazivanjem Stranica ili neki deo stranice se ne prikazuje očekivano.

Problemi sa zadatkom Neispravni primeri, neočekivana rešenja, postavka...

Problemi sa grader-om Dugo čekam na rezultat, ne dobijam rezultat...

Problemi sa sadržajem Greška u tekstu, neispravna formula...

Ostalo Ne mogu da se logujem, problem sa kontrolnom tablom...

Još detalja - opišite nam problem

Методичка збирка задатака из алгоритмике - одабрани алгоритми и структуре података

Алгебарски алгоритми
- Модуларна аритметика
  - Операције по модулу
  - Монопол
  - Разбрајалица
  - Збир бројева по модулу
  - Сат
  - Навијање сата
  - Степен по модулу
- Дељивост и прости бројеви
  - Број и збир делилаца
  - Прост број
  - Најближи прост број
  - Ератостеново сито
  - Збир простих прост
  - Број простих у интервалима
  - Као Голдбахов проблем
  - Велики прости бројеви
- Растављање на просте чиниоце
  - Растављање на просте чиниоце
  - Допуна до пуног квадрата
  - Производи потпуни квадрати
  - Аеромитинг
  - Маx нзд
  - Множење и кореновање
  - Број и збир делилаца
  - Ојлерова функција
  - Број децимала записа разломка у датој бројевној основи
  - Збир НЗД свих парова делилаца
- Теорија бројева
  - Савршени бројеви
  - Пријатељски бројеви
  - Прост број
  - Најближи прост број
  - Ератостеново сито
  - Збир простих прост
  - Велики прости бројеви
  - Број простих у интервалима
  - Растављање на просте чиниоце
  - Допуна до пуног квадрата
  - Производи потпуни квадрати
  - Највећи заједнички делилац
  - Број дељив свим бројевима од 1 до n
  - Билијар из ћошка
  - Ученици на истим седиштима
  - Модуларни инверз
  - Кинеска теорема
  - Билијар
  - Ојлерова функција
- НЗД и НЗС
  - Највећи заједнички делилац
  - Поклони у продавници
  - Број дељив свим бројевима од 1 до n
  - Исти остаци свих бројева
  - Билијар из ћошка
  - Торта
  - Ученици на истим седиштима
- Модификовани Еуклидов алгоритам и кинеска теорема
  - Модуларни инверз
  - Кинеска теорема
  - Билијар
- Модификовано Ератостеново сито
  - Савршени бројеви
  - Пријатељски бројеви
  - Збир експонената факторизације факторијела
  - Лиувилова функција
  - Мертенсова функција
  - Број делилаца производа
- Полиноми
  - Вредност полинома
  - Аритметика над полиномима
  - Множење полинома
Геометријски алгоритми
- Скаларни и векторски производ
  - Колинеарност и нормалност вектора
  - Колинеарне тачке
  - Са исте стране
  - Тачка у троуглу
  - Координате пресека дужи
  - Постојање пресека дужи
  - Јединственост пресека дужи
  - Пресек дужи и полуправе
  - Растојање тачке од праве
  - Растојање тачке од полуправе
  - Растојање две дужи
  - Сортирање дуж линије
  - Оријентисани угао
- Конструкције и детекције
  - Темена паралелограма
  - Темена правоугаоника
  - Да ли је ромб
  - Да ли је правоугаоник
  - Огледало
  - Центар уписаног круга
  - Ортоцентар троугла
  - Центар описаног круга
  - Темена троугла
  - Премештање троугла
- Многоуглови
  - Површина конвексног многоугла
  - Да ли је конвексан
  - Припадност тачке конвексном многоуглу
  - Конструкција простог многоугла
  - Припадност тачке простом полигону
  - Конвексни омотач
- Проблемски задаци
  - Површина полигона у првом квадранту
  - У којим квадрантима је троугао
  - Растав транслацијом
  - Такси растојање око правоугаоника
  - Растојање до квадра
  - Растојање по коцки, суседне стране
  - Растојање око круга
  - Број парова дужи
Графови
- Представљање графова и њихова елементарна својства
  - Листе повезаности
  - Матрица повезаности
  - Судија
  - Најпопуларнији сајт
- Обилазак (претрага) у дубину и ширину
  - Достижни чворови
  - Пећине
  - Престолонаследници
  - Пећине са тунелима
  - Коренско дрво
  - Компоненте повезаности
  - Да ли је бипартитан
  - Чудна мрежа
  - Авионска преседања
  - Змије и лестве
  - Тастатура
  - Косе црте
  - Аутобуске руте
- Тополошко сортирање
  - Редослед послова
  - Провера циклуса
- Најкраћи путеви од једног чвора
  - Најкраћи пут између два града
  - Кашњење сигнала
  - Најмање напорна стаза
- Најкраћи путеви измећу свих парова чворова
  - Сви најкраћи путеви у густом графу
  - Сви најкраћи путеви у ретком графу
- Минимално повезујуће стабло
  - Уштеда каблова
  - Кластери
  - Вода до сваке куће
Алгоритми текста
- Тражење узорка у тексту
  - Префикс суфикс
  - Подниска
  - Подниске
  - Немењајуће ротације
  - Периодичност ниске
- Најдужи палиндроми
  - Најдужа палиндромска подниска
  - Најкраћа допуна до палинрома
  - Најдужи подниз палиндром
- Регуларни изрази
  - Датуми у тексту
  - Бројевни литерали
- Формалне граматике
  - Превођење потпуно заграђеног израза у постфиксни облик
  - Вредност потпуно заграђеног израза
  - Вредност израза у коме нема заграда
  - Вредност израза
Напредне структуре података
- Префиксно дрво
  - Днк секвенце
  - Коректни телефони
  - Днк префикси
  - Различите подниске
  - Пар који даје највећи XOR
  - Највећи XOR сегмента
- Структура података за представљање дисјунктних подскупова (union-find)
  - Први пут кроз матрицу
  - Распоред са максималним збиром профита
- Упити распона
  - Статички упити распона
    - Збирови сегмената
    - Увећавање сегмената
    - Пермутација са највећим збиром упита
  - Сегментна дрвета
    - Суме сегмената променљивог низа
  - Фенвикова стабла
    - Суме сегмената променљивог низа
    - Увећања сегмената и читање елемената
    - К-ти парни број
    - Трик са картама
    - Инверзије након избацивања сегмената
    - Број различитих елемената у сегментима
  - Лења сегментна дрвета
    - Увећања и збирови сегмената

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

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

Излаз

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

Пример

Улаз

Излаз

Објашњење

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

Пример 2

Улаз

Излаз

Објашњење

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

Morate biti ulogovani kako biste poslali zadatak na evaluaciju.