Задача 1. Разность квадратов ≡

Условие

Вы участвуете в разработке программного модуля для системы символьных вычислений. Модуль будет использоваться для решения специального вида диофантовых уравнений.

По заданному целому неотрицательному целому числу n разрабатываемый модуль должен найти два натуральных числа x и y, для которых выполнено равенство x² − y² = n. Найденные числа не должны превышать 2⁶² − 1.

Требуется написать программу, которая по заданному целому неотрицательному числу n находит натуральные числа x и y, не превышающие 2⁶² − 1, разность квадратов которых равна n.

Формат входных данных

В единственной строке дано одно целое число n (0 ≤ n ≤ 2⁶⁰). Обратите внимание, что заданное во вводе число не помещается в 32-битный тип данных, необходимо использовать 64-битный тип данных (например, long long в C++, int64 в Паскале, long в Java).

Формат выходных данных

Если искомые x и y существуют, то необходимо вывести две строки: в первой строке выведите слово Yes, а во второй  — искомые x и y.

Если подходящих пар x и y несколько, можно вывести любую из них, но должно выполняться условие 1 ≤ x, y ≤ 2⁶² − 1.

Если решения нет, в единственной строке необходимо вывести слово No.

Ограничения

0 ≤ n ≤ 2⁶⁰

1 ≤ x, y ≤ 2⁶² − 1

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

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

3

Yes
2 1

2

No

Разбор

Во-первых заметим, что числа 1, 2 и 4 невозможно представить в виде разности двух квадратов.

Рассмотрим решения для первых двух подзадач: его время работы O(n).

Переберем все возможные числа x из интервала (1, 2¹⁰). Зная уменьшаемое и разность, найдем вычитаемое. Если число является квадратом, то ответ найден. Если ни одно число из вычитаемых не является квадратом, то ответа нет.

Для подзадачи 3 одно из решений такое: заметим, что x² − y² = (x − y) ⋅ (x + y). Переберём делители n, для каждого делителя p ≤ √n проверим, есть ли решение в целых числах для системы уравнений

{x − y = px + y = n / p

Если такое решение есть, мы нашли ответ. Интересно, что это решение легко модифицируется до O(1). Если x и y одинаковой четности, то их разность квадратов делится на 4, а иначе не делится на 2. То есть ответ для n, которые делятся на 2, но не делятся на 4 No.

Если n нечетное, то давайте попробуем решить такую систему уравнений:

{x − y = 1x + y = n{2 ⋅ x = n + 1x + y = n{x = n + 12x + y = n{x = n + 12y = n − 12

То есть ответ для нечётного n всегда есть, если n ≥ 3.

Если n делится на 4, то решим такую систему: {x − y = 2x + y = n2{2 ⋅ x = n2 + 2x + y = n2{x = n + 44x + y = n{x = n + 44y = n − 44 То есть ответ всегда существует, если n делится на 4 и больше 4. Заметим, что решение с перебором делителей автоматически найдёт указанные решения, если n не даёт остаток 2 при делении на 4. Таким образом для его доработки достаточно рассмотреть указанный случай. Наконец, не забудем, что 0 можно получить например из x = 1, y = 1