Задача заключается в нахождении простых чисел по версии капитана задан 27 Янв '14 20:02 ivan145
показано 5 из 8
показать еще 3
|
Мне имело смысл "прогнать" программу при максимальных значениях, чтобы понять, какое число вариантов надо рассматривать при самом "грубом" способе перебора. Оно составляет где-то почти 6 миллионов, а это многовато. Тем не менее, если программа работает 3 секунды вместо требуемой одной, то алгоритм или его реализацию всегда можно слегка улучшить, не внося "радикальных" изменений. Итак, я хочу начать с того, что при последовательных делениях на простые числа возникает определённое корневое дерево. Вверху находится число $%n$%. Из него идут вниз рёбра к вершинам $%[n/2]$%, $%[n/3]$%, $%[n/5]$%, ..., $%[n/p_m]$%. Число $%[n/2]$% мы далее делим с округлением на 3, 5, 7, 11, ..., и из него идут рёбра к соответствующим числам. И так на столько уровней вниз, пока числа после округлений остаются ненулевыми. Строить полностью это дерево в процессе вычислений не требуется. Нам нужно всего лишь обходить каждую из его вершин в определённом порядке. Когда мы впервые посещаем очередную вершину, то к общей сумме мы прибавляем число $%\pm v$%, где $%v$% -- число, соответствующее данной вершине. Оно меняет знак с плюса на минус и обратно при спуске или поднятии на один уровень. Запоминать в каждый текущий момент нам нужно только "ветку" дерева, ведущую из корня в просматриваемую вершину. Эта информация хранится в небольшом (менее 10 элементов) массиве. Вместе с числами (вершинами) в "параллельном" массиве мы запоминаем номер того простого числа, на который нам разрешено делить данное число $%v$%. Покажем это на примере $%n=100$%, когда делить приходится на четыре простых числа: 2, 3, 5, 7. Хранимую информацию я буду записывать в виде пар (это как бы два массива). Начальная запись (100;1) означает, что рассматриваемся число 100, которое можно делить на самое первое простое число списка, то есть на два. Делаем это, и добавляем в массив пару (50;2). Теперь уже делить можно только на 3. Добавляем новую пару (16;3). Следующей будет (3;4). Здесь уже делить больше нельзя, поэтому возвращаемся назад. При этом нет необходимости менять массив, а достаточно иметь одну переменную (скажем, d), которая нам указывает номер просматриваемого элемента массива. Возврат назад означает выполнение команды d:=d-1, то есть мы переходим к паре (16;3), превращая её в (16;4), так как на третье простое число мы уже делили. Теперь после деления на 7 мы добавляем в массив пару (2;5), увеличивая d на 1, после чего идём назад (то есть d:=d-1). Это нас возвращает к (16;4), но 4 есть номер последнего простого числа. Снова делаем шаг назад (d:=d-1), и рассматриваем пару (50;2), превращая её в (50;3) и переходя от неё вниз к паре (10;4) после деления на 5. И так далее. Думаю, описываемый процесс ясен, равно как и то, какие слагаемые в его ходе добавляются к общей сумме. Как я уже отмечал, для $%n$% порядка $%2\cdot10^9$% и для простых чисел в диапазоне 300, данное дерево имеет около $%6\cdot10^6$% вершин. Чтобы уменьшить это количество, увеличивая быстродействие программы в несколько раз, применим вот какое соображение. Можно с самого начала отдельно учесть числа, делящиеся на 2 или на 3. Их количество на любом отрезке вычисляется по очень простой формуле. Всё, что туда не вошло, входит в одну из двух арифметических прогрессий: $%6k+1$% или $%6k+5$%. Каждую из прогрессий далее будем рассматривать по отдельности на предмет того, какие числа в ней делятся на 5, на 7, на 11, и так далее, и какие значения $%k$% этому соответствуют. Значения $%k$% при этом идут подряд, а диапазон для них сократится в 6 раз. Прогрессий две, то есть выигрыш во времени примерно втрое уже имеется. На самом деле, он будет существенно больше, так как при построении дерева делить надо будет только на простые числа, начиная с 5. Числа начинают убывать очень быстро, и число вершин дерева в размерах тоже уменьшается. Последнее замечание касается подсчёта и суммирования. Допустим, нам надо понять, сколько членов прогрессии $%6k+5$% делится на, скажем, 17 при $%k$% от 2014 до 3000. Это несложная арифметическая задача: $%k$% должно при делении на 17 давать определённый остаток (в данном случае это 2), который в общем случае легко найти. И далее нужно подсчитать, сколько натуральных чисел удовлетворяет двойному неравенству $%2014\le17n+2\le3000$%, делается при помощи целочисленного деления. Полагаю, что изложенного будет достаточно для того, чтобы уложиться в требуемое время. Расход памяти здесь совсем небольшой. отвечен 29 Янв '14 19:41 falcao Можно с самого начала отдельно учесть числа, делящиеся на 2 или на 3. Их количество на любом отрезке вычисляется по очень простой формуле. Всё, что туда не вошло, входит в одну из двух арифметических прогрессий: 6k+1 или 6k+5. Каждую из прогрессий далее будем рассматривать по отдельности на предмет того, какие числа в ней делятся на 5, на 7, на 11, и так далее, и какие значения k этому соответствуют.Не совсем понимаю этот момент.Можно поподробней
(29 Янв '14 20:11)
ivan145
У меня в тексте это далее разъясняется на примере делимости на 17. То есть, с моей точки зрения, я всё как бы предусмотрел и разъяснил. Если Вам что-то из сказанного не очевидно, я готов дать дополнительные пояснения, но я должен знать, на какие вещи надо обратить внимание.
(29 Янв '14 20:21)
falcao
Допустим,мы учитываем числа делящиеся на 2.Посчитал их количество.Далее,вы говорите все,что туда не вошло входит в одну из арифметических прогрессий?Откуда взялись прогрессии?как понять все что туда не вошло?
(29 Янв '14 20:29)
ivan145
А, то есть вопрос относился к прогрессиям? Это соображение я считал очевидным, поэтому детально не стал описывать. Все целые числа входят ровно в одну из шести последовательностей вида 6k+r, где r есть остаток от деления на 6, то есть в одну из прогрессий. Числа вида 6k, 6k+2, 6k+4 чётны. Числа вида 6k+3 кратны трём. Когда мы это всё учитываем и отбрасываем, то остаются числа двух оставшихся прогрессий, то есть как раз 6k+1 и 6k+5. В них входит всё то, что не делится ни на 2, ни на 3. Такой учёт полезно сделать в самом начале, чтобы "выловить" самое "крупное".
(29 Янв '14 20:38)
falcao
Этот момент,теперь понятен.Далее я не понял почему остаток равен 2,и как с помощью целочисленного деления найти количество чисел,которые удовлетворяют этому неравенству
(29 Янв '14 21:02)
ivan145
Остаток в рассмотренном мной примере равен 2, так как $%6\cdot2+5=17$%. Его значение находится подбором. По второму вопросу: мы имеем границы для $%17n+2$%. Вычитаем 2, делим на 17. Получается, что $%n$% лежит между $%2012/17$% и $%2998/17$%. Целые части этих чисел находятся при помощи операции div. А остальное, я надеюсь, очевидно. Например, неравенству $%118,3...\le n\le176,3...$% удовлетворяют числа от 119 до 176 включительно, и их имеется 58.
(29 Янв '14 21:54)
falcao
На одном из форумов нашел следущее объяснение по этой задаче но не совсем его понял.Итак,что там говорят:Нас просят найти количество чисел от l до r, которые делятся на какое-то из первых k простых. Вообще, решение выглядит так: перебираем все подмножества из k элементов, смотрим, сколько чисел от l до r делятся на все числа из этого подмножества (то есть делятся на их НОК). Если подмножество было нечётной мощности, то прибавляем то количество к ответу, иначе вычитаем.
(30 Янв '14 9:41)
ivan145
Продолжаю.Можно заметить, что для многих подмножеств их НОК будет больше 2·109 и они не дают никакой вклад в ответ. Чтобы их по максимуму отсекать мы реализуем перебор так: набираем числа в подмножество, проходя по массиву с конца (начиная с самого большого простого до k). Всё что нужно знать о подмножестве это: чётность его размера, последнее не рассмотренное число и его текущий НОК. Соответственно, мы либо берём первое не рассмотренное число в наше подмножество и пересчитаем ответ с учётом этого, либо не берём и передаём подмножество дальше, только уже с другим первым не рассмотренным числом
(30 Янв '14 9:42)
ivan145
Как вы думаете,имеет ли это решение право на жизнь?И если да,не могли бы его объяснить поподробнее
(30 Янв '14 9:42)
ivan145
@ivan145: это заведомо неприемлемый подход хотя бы по причине того, что подмножеств мощности $%k$% имеется очень и очень много. Даже если бы бы стали перебирать все пары (не говоря о подмножествах мощности 60), то их количество могло бы иметь порядок типа $%10^{18}$%, то есть миллиард миллиардов. Для сравнения: в столетии меньше 4 миллиардов секунд.
(30 Янв '14 11:05)
falcao
показано 5 из 10
показать еще 5
|
Добавьте, пожалуйста, ссылку на предыдущее обсуждение этой задачи, потому что на него придётся ссылаться. Алгоритм будет предлагаться тот же, но с несколько убыстренной реализацией и с небольшим расходом памяти.
@Falcao,я добавил ссылку вы говорили что у вас есть что-то новое по задаче
@ivan145: прежде чем написать здесь, я хотел немного поэкспериментировать с программами. В Maple я написал алгоритм в несколько строк, но это очень медленная система. Хочу сравнить с тем, как будет в Паскале. Там обычно всё существенно быстрее происходит. Постараюсь завтра всё описать (в принципе, я мог бы и сейчас это сделать, но лучше всё-таки после "прогона" программы).
Пишу здесь,так как там занято.А дальше же написано,что берутся не все подмножества и описывается перебор с самого большого простого до k,там,вроде,тоже отсекаются варианты
@ivan145: я когда прочитал фразу "перебираем все подмножества", то дальше читать не стал. Сейчас я прочитал до конца, и стало понятно, что описывается та же самая процедура. НОК здесь совпадает с произведением, выбор знака плюс или минус определяется чётностью сомножителей. Разница только в том, что перебор начинается с деления на самые большие чисел, а не на маленькие. Но порядок разбора случаев не важен, так как сами случаи в точности те же. В общем, это эквивалентно тому, что я описывал в предыдущем обсуждении -- без учёта модификаций и улучшений.
Falcao,ваш алгоритм со списками оказался правильным,т.е. тот который вы написали до этого.Получилось так,что на одном из компиляторов он проходил за 1.046,что больше секунды и не пролезало по ограничению по времени,но на другом компиляторе все это заняло 0.718.Алгоритм,который вы предложили во второй раз я не реализововал,но думаю он будет как минимум быстрее раза в два.Спасибо)
Можно ли вопрос закрыть,по причине того,что он отвечен
@ivan145: да, там есть в списке пункт типа "вопрос отвечен, и ответ принят". Только условие убирать не надо, потому что становится непонятно, на какой вопрос отвечали.