Поиск

Генераторы квадратов


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

Множество $$$A = \{a_1, a_2, \ldots, a_k\}$$$ различных натуральных чисел с суммой $$$a_1+a_2+\ldots+a_k=n$$$ называется генератором квадратов, если сумма любых $$$k-1$$$ элементов этого множества является полным квадратом целого числа.

Например, множество $$$\{1, 22, 41, 58\}$$$ является генератором квадратов, так как $$$1 + 22 + 41 = 64 = 8^2$$$, $$$1 + 22 + 58 = 81 = 9^2$$$, $$$1 + 41 + 58 = 100 = 10^2$$$, $$$22 + 41 + 58 = 121 = 11^2$$$.

По заданным $$$n$$$ и $$$k$$$ постройте множество из $$$k$$$ различных натуральных чисел с суммой $$$n$$$, которое является генератором квадратов, либо выясните, что такого нет.

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

На ввод подаются два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 200\,000$$$, $$$2 \le k \le 30$$$).

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

Если искомый генератор квадратов существует, выведите «YES» на первой строке, а на второй строке выведите $$$k$$$ натуральных чисел — искомое множество.

Если генератора квадратов с заданными параметрами не существует, выведите «NO».

Пример

Входные данные
122 4
Выходные данные
YES
1 22 41 58

Раз сумма без любого слагаемого - полный квадрат, в качестве слагаемых можно использовать только числа вида n - x*x для целых x, обозначим их как b[1], b[2], …, b[t] Таких чисел порядка квадратного корня из n.
 
Надо почитать число способов представить n в виде суммы k слагаемых, каждое из заданного массива b.

Можно воспользоваться опять рекурсивным перебором вариантов.


def search(x, n, k, prefix):
    if k == 1:
        if n > prefix[-1] and n in terms_set:
            print("YES")
            print(*(prefix + [n]))
            exit(0)
        return
    if x == len(terms) or terms[x] * k > n:
        return
    search(x + 1, n - terms[x], k - 1, prefix + [terms[x]])
    search(x + 1, n, k, prefix)


n, k = map(int, input().split())
terms = []
for x in range(1, n):
    if x * x >= n:
        break
    terms.append(n - x * x)
terms.sort()
terms_set = set(terms)
search(0, n, k, [])
print("NO")

Для отправки решения задачи необходимо авторизоваться!

Разбор задачи