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


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


Условие задачи Прогресс
ID 31849. Несократимые дроби
Темы: Арифметические алгоритмы (Теория чисел)    Функция Эйлера   

Дробь \({m \over n}\) называется правильной несократимой, если \(0 < m < n\) и \(НОД (m, n) = 1\). Найдите количество правильных несократимых дробей со знаменателем n.
 
Входные данные 
В первой строке задается число знаменателей для которых надо найти количество правильных несократимых дробей N (\(N <=100\)). Каждая последующая строка число n (\(n < 10^9\)). 
 
Выходные данные 
Для каждого n в отдельной строке вывести ответ на поставленную задачу.
 

 

Примеры
№ Входные данные Выходные данные
1
4
23
23456
7
17
 
 22
11712
6
16

ID 33687. Функция Эйлера
Темы: Функция Эйлера   

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

Входные данные
На вход подается натуральное число n.

Выходные данные
Выведите ответ на задачу.
 

 

Примеры
№ Входные данные Выходные данные
1 2 1

ID 31850. Сумма функции Эйлера
Темы: Функция Эйлера   

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

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

Выходные данные 
Выведите ответ на задачу.
 

 

Пример
№ Входные данные Выходные данные
1 2 2 4