#111592

Темы: [НОД и алгоритм Евклида]

Известно, что запись числа A в позиционных системах счисления с основанием p и q имеет вид бесконечной периодической дроби с периодом 2:

A = 0, (ab) = 0, (ba) ( * ) где a и b - различные цифры в этих системах счисления.

Написать программу, которая для введенных натуральных чисел p и q находит и выводит все возможные пары значений цифр a и b, удовлетворяющих соотношению ( * ).

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

Даны два числа p и q (2 ≤ p < q ≤ 10⁵).

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

В первой строке выведите число k — количество пар a и b. Далее в n строках выведите эти пары (a < b). Пары следует выводить в порядке возрастания a, а если они равны, то в порядке возрастания b. Если пар нет, то k должно быть равно 0.

Примеры тестов

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

5 11

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

1
1 4

Примечание

Значением числа, запись которого в позиционной системе счисления с основанием s есть 0, cdef (где c, d, e, f - цифры), является $\text{[math]}$

#111593

Деление на сегменты

Темы: [НОД и алгоритм Евклида]

Определим множества K[i] рекуррентно. Пусть K[0] = [0, 1]. Разделим сегмент [0, 1] на три части точками $\text{[math]}$ и $\text{[math]}$ и удалим из него интервал $\text{[math]}$ . Получим множество K[1], состоящее из двух оставшихся сегментов $\text{[math]}$ и $\text{[math]}$ .

Каждый из них разделим на три части (точками $\text{[math]}$ и $\text{[math]}$ для первого сегмента, и точками $\text{[math]}$ и $\text{[math]}$ - для второго) и удалим средние интервалы $\text{[math]}$ и $\text{[math]}$ . Таким образом получаем множество K[2], и т.д.

Пусть мы построим множество K[i]. Поделим каждый оставшийся сегмент из K[i] на 3 части и удалим из этих сегментов средние интервалы. Получим, таким образом, из K[i] множество K[i + 1].

Вводятся 3 целых числа n, a, b. Необходимо определить, принадлежит ли точка с координатой $\text{[math]}$ множеству K[n].

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

Даны три натуральных числа n, a, b (1 ≤ n ≤ 10⁶, 0 ≤ a ≤ b ≤ 10¹⁸, b ≠ 0).

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

Выведите «YES» в случае, если точка $\text{[math]}$ принадлежит множеству K[n]. Иначе — выведите «NO».

Примеры тестов

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

1 2 4

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

NO

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

2 13 18

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

YES

#111594

Количество решений неравенства

Темы: [Перебор]

Дано натуральное n. Подсчитать количество решений неравенства x² + y² < n в натуральных числах, не используя действий с вещественными числами.

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

Дано одно число n (1 ≤ n ≤ 10¹²).

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

Выведите одно число — количество решений неравенства.

Примеры тестов

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

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

#111595

Совершенные числа

Темы: [Битовые операции]

Число называется совершенным, если оно равно сумме всех своих делителей за исключением его самого. Любое четное совершенное число представимо в виде

2^p - 1·(2^p - 1), где p — натуральное число, а $2^p — 1$ — простое число.

Найти двоичное представление для максимального совершенного четного числа меньшего введенного N.

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

Дано число N (7 ≤ N ≤ 10¹²).

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

Выведите ответ на задачу в одной строке.

Примеры тестов

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

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

#111596

Химическая реакция

Темы: [НОД и алгоритм Евклида]

Заданы натуральные числа e, k, m, t в записи химической реакции

ХеАk + Y → YmAt + X где A, X, Y — атомы или группы атомов. Написать алгоритм, который находит такие натуральные коэффициенты, чтобы знак "стрелки" можно было заменить знаком равенства. Напомним, что эти коэффициенты должны быть несократимы.

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

Даны четыре натуральных числа (1 ≤ e, k, m, t ≤ 10⁹)

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

Выведите четыре числа — коэффициенты перед слагаемыми уравнения в порядке слева направо.

Примеры тестов

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

2 3 5 6

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

2 5 1 4

Примечание

Исходный пример соответствует уравнению 2X_2A₃ + 5Y = Y_5A₆ + 4X