#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¹²).

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

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

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

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

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

#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

#111597

Площадь треугольника

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

Вводятся целые числа a и b. Пусть у треугольника ABC координаты A = (0, 0), B = (a, b), а обе координаты C = (x, y) - целые числа, и площадь треугольника ABC не равна нулю.

Какую минимальную площадь может иметь треугольник ABC?

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

Даны два целых числа a и b, по модулю не превосходящие 10⁹. (a² + b² > 0)

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

Выведите одно число — минимальную возможную площадь треугольника ABC с точностью 10^- 9. То есть ответ будет считаться правильным, если будет отличаться от ответа жюри менее, чем на 10^- 9

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

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

4 0

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

2.0