Abay Baimukanov


Задача №1. 

Задача H. Легкая математика

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

У Абая есть натуральное число $n$. Он может делать с этим числом 2 вида операций: 1) Умножить $n$ на $x$ ($x$ — любое натуральное число) 2) Заменить $n$ на $\sqrt{n}$ (в этом случае $\sqrt{n}$ должно быть целым числом) Обе операции можно делать любое количество раз. Помогите Абаю узнать, какое минимальное число можно получить, выполняя данные операции. Также Абая интересует, какое минимальное количество операций нужно проделать, чтобы получить минимальное число.
Формат входного файла
В единственной строке дано натуральное число $n$ ($1 <= n <= 10^6$).
Формат выходного файла
Выведите два числа: минимальное число, которое можно получить, затем минимальное количество операций для получения этого числа.
Примеры:
Вход
20
Ответ
10 2
Вход
5184
Ответ
6 4
Замечание
Ответ для первого примера: 20 --> $20 \times 5 = 100$ --> $\sqrt{100} = 10$ — в итоге 2 операции. Ответ для второго примера: 5184 --> $\sqrt{5184} = 72$ --> $72 \times 18 = 1296$ --> $\sqrt{1296} = 36$ --> $\sqrt{36} = 6$ — в итоге 4 операции. ( Abay Baimukanov )
комментарий/решение(6) олимпиада
Задача №2. 

Задача H. Легкая математика

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

У Абая есть натуральное число $n$. Он может делать с этим числом 2 вида операций: 1) Умножить $n$ на $x$ ($x$ — любое натуральное число) 2) Заменить $n$ на $\sqrt{n}$ (в этом случае $\sqrt{n}$ должно быть целым числом) Обе операции можно делать любое количество раз. Помогите Абаю узнать, какое минимальное число можно получить, выполняя данные операции. Также Абая интересует, какое минимальное количество операций нужно проделать, чтобы получить минимальное число.
Формат входного файла
В единственной строке дано натуральное число $n$ ($1 <= n <= 10^6$).
Формат выходного файла
Выведите два числа: минимальное число, которое можно получить, затем минимальное количество операций для получения этого числа.
Примеры:
Вход
20
Ответ
10 2
Вход
5184
Ответ
6 4
Замечание
Ответ для первого примера: 20 --> $20 \times 5 = 100$ --> $\sqrt{100} = 10$ — в итоге 2 операции. Ответ для второго примера: 5184 --> $\sqrt{5184} = 72$ --> $72 \times 18 = 1296$ --> $\sqrt{1296} = 36$ --> $\sqrt{36} = 6$ — в итоге 4 операции. ( Abay Baimukanov )
комментарий/решение(6) олимпиада
Задача №3. 

Задача C. From And with love

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Абай очень любит массивы. Еще больше он любит играть с подпоследовательностями массива. Подпоследовательность — это такая последовательность массива, которая может быть получена удалением нескольких (возможно ноль) элементов из этого массива. Вам дан массив $A$ из $N$ целых чисел. Рассмотрим какую--нибудь подпоследовательность массива. Пусть битовый AND этой подпоследовательности равен $X$. Тогда подпоследовательность называется хорошей, если в ней нет элемента со значением $X$. Посчитайте количество хороших подпоследовательностей.
Формат входного файла
В первой строке дается натуральное число $N$ — размер массива $A$. В следующей строке заданы $N$ целых неотрицательных чисел — элементы массива $A$.
Формат выходного файла
Выведите одно число — количество хороших подпоследовательностей. Так как ответ может быть достаточно большим, выведите его остаток от деления на $10^9 + 7$.
Система оценки
Это задача состоит из 5 подзадач и 25 тестов, каждый тест оценивается в 4 балла:
  1. $1 <= N <= 15$, $0 <= A_i < 2^{20}$. Тесты 1 -- 3
  2. $1 <= N <= 10^5$, $0 <= A_i < 2^4$. Тесты 4 -- 7
  3. $1 <= N <= 10^5$, $0 <= A_i < 2^{10}$. Тесты 8 -- 12
  4. $1 <= N <= 10^5$, $0 <= A_i < 2^{15}$. Тесты 13 -- 18
  5. $1 <= N <= 10^6$, $0 <= A_i < 2^{20}$. Тесты 19 -- 25
Пример:
Вход
5
0 2 5 3 7
Ответ
6
Замечание
Одной из хороших подпоследовательностей является 2, 5, 7. Ее битовый AND равен 0, при этом число 0 не присутствует среди 2, 5, 7. Операция побитового AND существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string&$>>, в Pascal — как <>. Таблица для побитового AND.\\ 1 $and$ 1 = 1, 1 $and$ 0 = 0\\ 0 $and$ 1 = 0, 0 $and$ 0 = 0\\ ( Abay Baimukanov )
комментарий/решение олимпиада