Вчера, готовясь к зональной олимпиаде, я прорешивал задачи прошлых лет и наткнулся на одну сложную задачу. Мне ее так и не удалось решить, однако некоторые идеи у меня появились. Рассмотрим первые k простых чисел(k > 1). И скажем, что каждое из выведенных чисел должно будет делиться на каждое из этих простых чисел.
*C(n, k) — количество сочетаний из n по k.
Теперь поймем, что у нас существует C(k, t) чисел, удовлетворяющих условиям. На каждое сочетание сопоставим число. Выбранные простые числа(t штук) возведем в квадрат, остальные у нас будут в первой степени. Несложно понять, что все такие числа нам подходят. Однако, сколько я не подбирал такие k и t, что C(k, t) >= 1000 ((13;5), (13;6), (14;4)), у меня некоторые числа были больше 2^63 — 1.
Пожалуйста, помогите с решением.
UPD: Ripatti предложил отличную идею, которая хорошо описана в его неоправданно заминусованном комментарии в upd2. Задача теперь проходит 24/25 тестов, при n <= 975. Последний тест так и не покорился мне.
UPD2: Действительно, данная модель, предложенная Ripatti проходит только при n <= 975. Пример для n = 975: k = 10, t = 23, a: (4, 3, 2, 1, 1, 1, 1, 1, 1, 1). Все разумные a, k и t были проверены. Не нужно забывать, что мы отсекаем все варианты, которые превысили 2^63-1.
UPD3: С радостью вам сообщаю, что задача решена! Спасибо огромное за это Ripatti и alexey.enkov! Попробуйте решить ее самостоятельно. Она того стоит:)
