Какое наименьшее число n можно представить в виде произведения n = a∙b ровно k способами? Произведения a∙b и b∙a считаются одним способом, все числа натуральные (1 ≤ k ≤ 50).
Лимит времени: 1 секунда
Лимит памяти: 64 MB
Пришла мысль генерировать данное число (n) произведением нескольких простых чисел, но я не могу понять, каким образом выбирать эти числа. Написал программу(полный перебор), определил некоторые числа и их разложения, но закономерности не заметил.
Заранее спасибо.
Задача взята отсюда: http://www.e-olimp.com/problems/5
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 1 | maomao90 | 161 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | -is-this-fft- | 148 |
| 5 | SecondThread | 148 |
| 5 | atcoder_official | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | TheScrasse | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.07.2024 00:16:50 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
два раза повторенная шутка - уже не шутка
На самом деле, интересно, сколько раз freopen создавал тред "памагите ришить зодачу", пока был совсем зеленым?
Он не просил поднять за него штангу!
2k+12k-1 делитель, и выбрать из них минимальное. Обозначим число делителей за x. Разложим x на множители всеми возможными способами (при данных ограничениях их не очень много), дальше каждому множителю припишем простое число. Очевидно, надо приписывать минимальные простые числа, причем так, чтобы меньшим простым числам соответствовали большие количества. Если непонятно, спрашивайте, уточню.Пусть есть некоторое число
a = p1a1p2a2p3a3... pnan
Количество его делителей
не зависит от простых чисел в разложении a.
Теперь. Если у числа c делителей, то подобных разложений ⌈ c / 2⌉, значит, число делителей искомого числа 2k или 2k-1.
Для заданного количества делителей надо перебрать все невозрастающие разложения в произведение сомножителей и использовать их без единицы как степени для 2, 3, 5, 7, 11, ... соответственно. Лучшее найденное число будет ответом.
Так, если k = 2, то делителей у искомого числа 3 или 4.
3 = 3, это соответствует 23 - 1 = 4.
4 = 4, это соответствует 24 - 1 = 8.
4 = 2*2, это соответствует 22 - 1 * 32 - 1 = 6.
Ответ 4.
P.S. http://www.e-olimp.com/problems/5
А вообще вопрос ко всем: а уверены ли Вы что в это время в каком-нибудь другом месте эта задачке где-то не играет?
Кстати, как и прошлая геометрическая задачка Петра Митричева из acmp.ru ?
Вопрос второй: а как же авторские права? На Codeforces прописано, что Вы бережёте авторские права задач, размещённых на Вашей платформе и никоим образом их нельзя использовать на других платформах.
А в данном случае почему нет уважения к авторским правам другой платформы?
Этот пост не с точки зрения предъявления претензий, а так, как любит писать anonymous - "задачка просто для подумать..." :)
Неужели она ни о чём Вам не говорит?
1. Некоторые личности совершенно не умеют даже правильно копипастить
2. Можно прогнать свой код на тестирующей системе
3. Можно определить, не идет ли сейчас контест с этой задачей
4. Нет ли там форума, на котором разжевано до мелочей и куда можно просто дать ссылку
и т.д.
Просто реально я полностью поддерживаю тех, кто не отвечает на подобные вопросы. Ибо положительный ответ в большинстве случаев это "медвежья услуга".
Идея решения (основная теорема арифметики) указана на сайте.
Так неужели трудно было самому поискать что это за штука и как её реализовать?
А зачем? Гораздо проще задать вопрос на любом сайте для программистов и там процентов на 50 может и ответят, а на Codeforces этот процент вероятности получения ответа намного больше.
Так зачем самому голову напрягать, если это могут сделать другие товарищи? :)
Скорее претензии к явлению "группового решательства", как явлению... :)
Подсказка к одной из задач для самостоятельного решения.
Где это написано? Чтобы такое написать, у CF должен быть договор с автором контеста (задачи) на передачу прав интелектуальной собственности, нет?
А обсуждение задач текущего соревнования если кто-то и должен отслеживать, то разве что организаторы этого соревнования. Иначе получается, что обсуждать нельзя вообще никакие опубликованные задачи — мало ли кто решил в этот момент устроить из них контест или дать в качестве домашнего задания.
Например, алгоритмы, детали реализации, участки кода не могут быть запатентованы на территории РФ.
-----edit-----
Имеется ввиду авторское право "вам нельзя делать то же самое, засужу!"
Копипаста - это другой вопрос.
(Думаю простят на с Вами юристы и юристки за саморекламу)
Зря
Тут решение выше неприменимо.Тут фиг его знает :).Делителей исходного числа не больше 1000.
В среднем у них делителей мало будет.
Динамика ленивая. Числа длинные. Для ускорения используется расчет рядом в логарифмах.
100% заходит.