Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Несократимые дроби

Арифметические алгоритмы Функция Эйлера

Дробь \({m \over n}\) называется правильной несократимой, если \(0 < m < n\) и \(НОД (m, n) = 1\). Найдите количество правильных несократимых дробей со знаменателем \(n\).
 
Входные данные: В первой строке задается число знаменателей для которых надо найти количество правильных несокртимых дробей N (N <=100). Каждая последующая строка число n (n < 109). 
Выходные данные: Для каждого n в отдельной строке вывести ответ на поставленную задачу.
Примеры:
Входные данные Выходные данные
1
4
23
23456
7
17
 
22
11712
6
16

Функция Эйлера

Функция Эйлера

Дано натуральное число \(n  <= 10^9,\) определите количество натуральных чисел, меньших \(n\) и взаимно простых с \(n\). Это число обозначается \( f(n) \)и называется фи-функцией Эйлера. Сложность алгоритма должна быть \( O(\sqrt{n})\) .

Примеры:

Входные данные Выходные данные
1 2 1

Сумма функции Эйлера

Функция Эйлера

Посчитать сумму функций Эйлера вида: \(\phi(1) + \phi(p) + \phi(p^2) + ... + \phi(p^\alpha)\),  где  \(p\)  - простое число, \(\alpha\)-  натуральное число

Входные данные: в одной строке через пробел подаются два числа \(p\) и \(\alpha\)  (\(p <=11,   \alpha  <=60 \)
Выходные данные: выведите ответ на задачу

Примеры

Входные данные Выходные данные
1 2 2 4