|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
17.03.2015, 17:45 | #1 |
Пользователь
Регистрация: 24.08.2014
Сообщений: 15
|
Олимпиадная задачка - найти K минимально близкое ( разницей сумм делителей + разность самих чисел) к заданному числу N
Всем здравствуйте.Помогите пожалуйста разобраться с задачей.Не знаю даже с чего начать ,подросте хоть какие-нибудь идеи.Заранее спасибо)
Вот условие: В сказочной стране СВУД очень любят решать различные математические задачи. Не так давно в одном из университетов СВУД была придумана следующая задача. Пусть имеется некоторое натуральное число N и существует некоторое натуральное число K, отличное от N. Обозначим сумму всех делителей числа N через SN, а сумму всех делите-лей числа K через SK (в суммы SN и SK не входят сами числа N и K). Найдем модуль разно-сти N и K, и модуль разности SN и SK, . Само число K выбрано при этом таким образом, что сумма этих модулей является минимально возможной. Например, пусть N = 18. Тогда SN = 21 (1+2+3+6+9 = 21). Число K, удовлетворяю-щее условиям задачи, будет равно 20. Действительно, SK = 22 (1+2+4+5+10 = 22). Поэтому . Для других чисел такая сумма будет больше 3, поэтому K = 20 – искомое число. Оригинального решения такой задачи пока еще никто из жителей СВУД не пред-ложил. Помогите жителям СВУД найти решение этой увлекательной задачи. Входные данные: В первой строке входного файла INPUT.TXT записано одно це-лое число N, причем 3 ≤ N ≤ 107. Выходные данные: В выходной файл OUTPUT.TXT нужно вывести число K, удо-влетворяющее условиям задачи. Дополнительные требования: время счета – не более 5 минут; при превышении от-веденного лимита времени будут назначены штрафные баллы. Примеры № INPUT.TXT OUTPUT.TXT 1 900 1050 2 5040 5760 3 75600 81900 4 362880 372960 5 1000000 998900 |
17.03.2015, 18:16 | #2 |
Пользователь
Регистрация: 24.08.2014
Сообщений: 15
|
Мне пришла идея,но не совсем получается ее реализовать.
Ясно,что K будет находиться недалеко от N , оно будет N/2<k<N*2 вот что получилось: может я что упускаю,подскажите пожалуйста. Код:
|
17.03.2015, 20:28 | #3 |
Старожил
Регистрация: 17.11.2010
Сообщений: 19,042
|
Код:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
18.03.2015, 09:50 | #4 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,238
|
Цитата:
Цитата:
НО! На мой взгляд, для чисел до 10 миллионов (10^7) простой перебор не очень эффективен. Тут хорошенько подумать надо... |
||
18.03.2015, 10:16 | #5 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 19,042
|
Цитата:
PS Если учитывать парные делители, то все будет Ok, так что я не прав
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 18.03.2015 в 10:40. |
|
18.03.2015, 10:38 | #6 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,238
|
Цитата:
Я ошибся!! Такое ограничение допустимо ТОЛЬКО для простых чисел. т.е. если до корня из A не было делителей (кроме единицы, конечно), тогда больше делителей и не будет. (для проверки на простоту числа это подходит). Но в данном случае, конечно, придётся перебирать до a div 2 а оценить время поможет такой тупо переборный код: Код:
т.е. это тупиковое направление для решения данной задачи... |
|
18.03.2015, 11:02 | #7 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Ниче не понял.. Ну делится 100 на 50 и что? Мы ж будем под два делителя брать..
Упс.. Заметил P.S Пардон А давайте так бахнем : посчитаем для всех n из 0..10^7.. Потом отсортируем.. И найдем бинарным наш.. За 10 часов просчитает.. Ах да.. На кнопку правка не попадаю(ибо гадкий планшет), поэтому склейте пжалста.. Последний раз редактировалось Serge_Bliznykov; 18.03.2015 в 13:14. |
18.03.2015, 11:12 | #8 |
Старожил
Регистрация: 17.11.2010
Сообщений: 19,042
|
А вот как себя ведет эта аликвотная сумма (термин в вики нашел) до n=1000. Очень похоже, что N/2<k<N*2 слишком большой интервал. А какой брать - вопрос
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
18.03.2015, 11:24 | #9 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
А интересно, насколько быстро можно из простых множителей получить сумму делителей
|
18.03.2015, 12:15 | #10 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 19,042
|
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Вычислить произведение чисел, неравных заданному числу Z | Hug | Помощь студентам | 4 | 12.11.2013 23:27 |
найти кол-во трехзначных чисел сумма простых делителей которых кратна 5 (на Делфи) | anzorchik | Помощь студентам | 2 | 02.10.2011 16:18 |
Определить ближайший элемент массива к заданному числу | wowan | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 28.05.2011 23:21 |