Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

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

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

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

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

Примеры

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

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

✓ 255✗ 442500лёгкаяВойти и решать

Применение Малой Теоремы Ферма#31866

Дано число a и простое число p. Найти такое минимальное число x, что \((a * x) \% p = 1\).

Входные данные
На вход подаются два натуральное числа a, p (\(a,\ p <= 10^{18} \)).

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

Примеры

№	Входные данные	Выходные данные
1	2 5	3

Малая теорема Ферма

✓ 263✗ 1 128600лёгкаяВойти и решать

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

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

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

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

Пример

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

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

✓ 199✗ 389400лёгкаяВойти и решать

Несократимые дроби#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

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

✓ 215✗ 234600лёгкаяВойти и решать

Банды Фомина №2#30699

Банда Фомина состоит из n групп, в каждой из которых a_i человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).

Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел a_i (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – l_i и r_i (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.

Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	6 1 3 7 1 4 100 3 1 3 3 4 2 6	21 7 8400

Быстрое возведение в степень Малая теорема Ферма Остатки Префиксные суммы(минимумы, ...)

✓ 11✗ 821 100средняяВойти и решать