Вчера, готовясь к зональной олимпиаде, я прорешивал задачи прошлых лет и наткнулся на одну сложную задачу. Мне ее так и не удалось решить, однако некоторые идеи у меня появились. Рассмотрим первые 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! Попробуйте решить ее самостоятельно. Она того стоит:)
Если взять 10 первых простых, но несколько из них брать не в квадрате(2, например, брать в степенях от 4 до 7), то можно так подобрать, что их будет не менее тысячи.
Да, я и так пытался. Можно даже взять 8 первых простых чисел и степени от 3 до 5. (C(8, 7) * C(7, 6) * C(6, 3) = 1120). Но это все равно вылетает за 2^63 — 1.
Почему ты именно t чисел возводишь в квадрат? Можно же выбирать любое количество чисел от 1 до k. И тогда у тебя 2^k — 1 вариантов. Я думаю, что будет достаточно первых 10 или 11 простых чисел.
UPD. Понял, что это не правильно.(Некоторые числа будут делиться)
те числа, что больше 2^63, можно просто выкинуть. возможно, тех, что останется, штук 1000 да наберется...
upd. половина поста бред, ее удалил.
upd2. а не, погодите, из этого бреда можно получить что то хорошее. давайте брать каждое простое число из какого-то промежутка [a_i ... 2*a_i] (для i-го простого числа a_i свое). причем будем брать только те числа, для которых сумма степеней равна некоторой константе.
например, вы сейчас рассматриваете частный случай такой модели — все a_i = 1, a искомая сумма равна t.
любые 2 числа такого вида подходят: возьмем 2 таких числа, тогда для некоторого i степень p_i больше степени p'_i. по принципу дирихле найдется такое j, что степень p_j меньше степени p'_j.
имхо в такой модели можно подобрать побольше нужных чисел. особенно если для маленьких p_i брать a_i побольше, а для других больших p_i — поменьше...
Не наберется. Проверял
upd1: Интересно наблюдать, как комментарий набирает сначала около -12, потом +9. Никогда такого не видел)
до -6 там не было upd2, поэтому, в принципе, было за что минусовать.
до -12 он добрался по инерции согласно принципу "видишь минус — не читай, минусуй".
наверно как то так)
а вообще, наверно мне надо было upd2 поместить в отдельный комментарий.
потому что я нарушил правило, которое выскакивает, когда жмешь "Ред."
Я когда-то пытался сдать эту задачу именно так. Но так и не смог из-за переполнения. Мне кажется там должна быть еще какая-то идея кроме масок одинаковой длины.
Есть еще одна очень странная идея, но все же имеющая право на существование. Идея состоит в следующем. Выберем первые k простых чисел. Выпишем все-все числа, влезающие в ограничения, которые образованы нашими простыми числами в разных степенях. Эти числа — вершины нашего графа. Ребро между двумя числами будет в том случае, если они удовлетворяют условию задачи. (v не делится на u, и v^2 делится на u. И наоборот). Нам нужно найти клику размера n. Кто-нибудь может решить эту задачу за полиномиальное время? Или хотя бы за разумное время(Предподсчет никто не отменял:) )
Главные идеи уже были высказаны выше ;-)
Делаем так: степень двойки может быть от 3 до 6, степень тройки от 2 до 4, степень каждого из последующих 9 простых от 1 до 2. Хотим сумму степеней 19 (чисел с такой суммой степеней -- 1549).
В этом случае, самое большое число, которое может получиться -- 2406725881560, что сильно меньше ограничения.
UPD. Да, лажа. Но, вполне верится, что если подкрутить коэффициенты, то все получится.
2406725881560 — это, к сожалению, самое маленькое число, которое может получиться. А самое большое — это его квадрат...
Я тут пока что накрутил так, что получается 975 чисел... Больше что то не хочет накручиваться
А школьники чуть выше заминусили эту идею, лол
upd. перебор по всем разумным a_i показал, что 975 — это максимум. т.е. больше в текущей модели не накрутишь, надо придумывать что то еще...
К этим 975 числам можно добавить некоторые из тех, где сумма степеней на 1 меньше. (За счёт тех, которые отсеклись по ограничениям). Например, точно можно добавить числа с суммой степеней на 1 меньше, от 2^62 до 2^63.
действительно, таких нашлось аж 38 штук (я проверил сразу все, где сумма степеней на 1 меньше).
итого получается 1013 чисел, и можно считать, что задача решена)
Я построил решение с 1015 числами, и вероятно это решение максимального размера
Если не ошибаюсь, мне жюри на очень древних весенних Питерских сборах говорило, что они умеют строить ответы для n ≤ 1043 (или что-то такое).
Я перебрал все возможные наборы a2>=a3>=a5.. для которых чисел в нужном диапазоне будет >= 1000 и для каждого нашел максимальную антицепь — 1015 получился максимальным, набор [4, 3, 2, 1, 1, 1, 1, 1, 1, 1]
Я так же построил для n = 1015, добавив к числам с суммой степеней на 1 меньше еще числа с суммой степеней на 2 меньше. Это было просто) Если добавлять в обратном порядке, то получится 1011. И это наводит на мысль о том, что можно выписать все эти 3(а то и больше) комплекта чисел, и выбрать из них максимальное подмножество, удовлетворяющее условию.
Усовершенствуем исходную идею про k простых чисел. Будем брать не простые, а произвольные числа. Тогда количество полученных чисел также будет C(n,k) но могут добавиться равные числа, их можно отсекать простым перебором. Те числа которые больше 2^63-1 мы просто игнорируем. И теперь заметим, что можно брать различные k. Для n <= 1000 такое проходит.
Пусть основания — 2, 3 и 6, k=2. Тогда 2*3=6 делит 6^2=36
Видимо не совсем подробно объяснил. Пусть у нас есть M чисел: A1, A2, ..., Am. Пусть есть число K(1 <= K < M). Рассмотрим сочетание С(M, K) : B1, B2, ..., Bk(1<=Bi<=M). Число, которое будет кандидатом на добавление будет получатся следующей формулой: X = A1*A2*...*Am*A[B1]*A[B2]*...*A[Bk]. Если X не делится ни на одно из полученных чисел, то добавляем его в ответ. Очевидно, что все полученные числа будут удовлетворять условию. Теперь будем использовать несколько различных K и тогда при n <= 1000 такие числа найдутся.
Такое решение проходит? Мне неочевидно почему такая жадность найдет нужное количество чисел
Этот способ написан в "Методических указаниях к решению". Не могу точно сказать, что он пройдет, но видимо можно подобрать такие Ai и такие K к ним, чтобы оно прошло.