|
|
|
|
|
|
|
| 1 Сташевский Александр Витальевич, 26 октября 2025 г. 11:48:39 |
| 2^(p - 1) * (2^p - 1), где p и 2^p - 1 - простые числа
|
|
|
| 2 Кенжегулов Арсен Кежегулович, 05 ноября 2022 г. 21:22:52 |
| можно 6 тест
|
|
|
| 3 Зинов Вадим, 20 августа 2020 г. 2:58:26 |
| Пришлось минуту ждать чтобы получить данные для перекалка. Искать готовые данные на внешних сайтах считаю глупо.. Вы тут учитесь решать задачи, а не обманывать сами себя.
|
|
|
| 4 Завгородний Михаил Сергеевич, 22 марта 2018 г. 18:34:02 |
| Изи, потому что совершенных чисел мало. Я их вычислил без программы, и записал в массив. Подсказка: в этой задаче всего 8 совершенных чисел.
|
|
|
| 5 Монтеверде Авраам Соломонович, 21 июля 2017 г. 22:23:52 |
Есть интересная теорема, доказана Эйлером:
Любое чётное совершенное число представимо в виде 2^(p - 1) * (2^p - 1), где 2^p - 1 --- простое. Кроме того, до 10^{около тысячи} доказано, что не существует нечётных совершенных чисел.
Теорему Эйлера можно попробовать доказать самому, вполне нормально по сложности. Верно, кстати, и обратное утверждение: Чётное число, представимое в виде 2^(p - 1) * (2^p - 1) где 2^p - 1 --- простое, является совершенным.
Поэтому достаточно проверять все числа вида 2^p - 1 на простоту. Замечу, что Мерсен доказал, что если 2^p - 1 -- простое, то p -- простое. Так что можно проверять только для простых p.
Так как по условию размер чисел ограничен unsigned long long, то, раз уж наши числа имеют вид 2^(p - 1) * (2^p - 1), понятно, что достаточно проверить до p = 33. Получать степени двойки быстро мы имеем битовым сдвигом.
Вот, собственно, и всё решение.
|
|
|
| 6 Герман Ален, 29 июня 2016 г. 13:28:09 |
| А это нельзя както решить без констант? Чтобы программа сама перебирала?
|
|
|
| 7 Данилыч, 11 августа 2015 г. 18:33:40 |
Сделал переборчик на маленьких числах, выявил закономерость — (2^ i)*((2^(i+1)) -1),
где "(2^(i+1))-1" — простое число, и сдал... почти. Всего чисел 8, а я поставил только 7... Обидно((
Щас за вывод возьмусь.
Если действовать через вывод формулы, то задача сложненькая получится. Кстати каждому совершенному числу соответствует ещё одна формула — сумма степеней от 2^x, до 2^(2*x).
К примеру:496=2^4+2^5+2^6+2^7+2^8
|
|
|
| 8 Клочков Антон Павлович, 09 июля 2015 г. 18:06:36 |
| Хорошая задача! Главное, сесть и подумать. Не обязательно гуглить эти числа. Вот, если я не ошибаюсь, то мой алгоритм работает за время O(N^(5/19)). Если я ошибся, администрация, извините:)
|
|
|
| 9 Сафаров Шахбоз Джумьаевич, 11 июня 2015 г. 15:53:06 |
| да еще дали сложность 51%!!! пффф....
|
|
|
| 10 Сафаров Шахбоз Джумьаевич, 11 июня 2015 г. 15:52:04 |
| Для лентяев: прогонять список всех совершенных чисел в массив(http://acmp.ru/article.asp?id_text=848) потом вывести. Для особо одаренных лентяев: воспользоваться классом BigInteger из java. Не понимаю что за задача, если решение уже есть в этом же сайте? АДМИН?
|
|
|
| 11 Штыря Алексей, 11 января 2014 г. 1:23:23 |
Алтыбай Назарбек, 18 февраля 2013 г. 19:55:00
2 ^ (p - 1) * ((2 ^ p) - 1) - совершенное число. Здесь, p - простое число.
Под эту формулу не подходят 11,23,29. Их не нужно учитывать. Из них совершенных чисел не выходит
|
|
|
| 12 Алтыбай Назарбек, 18 февраля 2013 г. 19:55:00 |
| 2 ^ (p - 1) * ((2 ^ p) - 1) - совершенное число. Здесь, p - простое число.
|
|
|
| 13 Ламзин Олег, 11 марта 2011 г. 22:37:44 |
да!!
легкая задача
особенно если знаеш как ее делать!!!
|
|
|
| 14 Козел Антон, 14 января 2011 г. 14:40:29 |
| ппц 20 минут не проходила потому что переменную не обнулил :|
|
|
|
| 15 ViruZ, 08 ноября 2010 г. 12:50:10 |
задача на то кто найдет эти числа в гугле... -_- не сказал бы что она на 51%... искать эти числа вручную прсто анрил=)
нормально они ищутся вручную, если использовать одно из свойств совершенных чисел.
|
|
|
| 16 Радченко Евгений Вячеславович, 16 июля 2010 г. 23:48:48 |
Когда я использовал не целочисленные типы, то 8 число не проходило 10 тест, как потом выяснилось, по причине того, что 8 число выводило на 2 больше, чем нужно. Поставил int64 - ACCEPTED.
Вы не знаете, почему так произошло, ведь по-моему в диапазоны типов double и real 5*10^18 должно вместиться?
|
|
|
| 17 Астраханцев Никита Юрьевич, 13 октября 2009 г. 8:46:57 |
| Непонятно, кстати, почему у задачи такой высокий процент сложности^_^ Кажется, она намного проще некоторых даже тридцати и двадцати - процентных задач.
|
|
|
| 18 Синёв Алексей Аркадьевич, 05 февраля 2009 г. 18:13:52 |
а число 1 является совершенным?
разумеется, что нет. вы вероятно не дочитали первое предложения условия задачи. сумма делителей числа 1, МЕНЬШИХ САМОГО ЕГО равно нулю, т.к. в принципе делителей меньше 1 не существует. а делители мы обычно полагаем, что числа не отрицательные.
|
|
|
| 19 shtirlitzzz, 15 января 2009 г. 20:36:52 |
Совершенных чисел не бесконечность. Это не доказано.
Да, но скорее всего их бесконечно много.
|
|
|
| 20 Федотов Максим Юрьевич, 15 января 2009 г. 20:25:47 |
| Интересно, как это 100 лет Вы насчитали...
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
