Из кулуаров олимпиады по программированию

[taki_net]

Феерическое читерство

Рассказ слышал от одного из ребят. Итак, задача: даны два числа
k<n<10^6. Вывести в выходной файл число n, равное количеству простых чилел, лежащих между k и n.

Ограничение на память стандартное - 64Мбайт, на время работы - 2 с. Причем эксперимент показывает, что пересылка в памяти 10^8 элементов массива в тот же или другой массив занимает около 1 с, т.е. алгоритм, требующий порядка
n * n^0,5 операций (т.е. 10^9) не проходит ограничение по времени.

Внезапно одна из команд сдает решение, которое выполняется малые доли секунды и на всех тестах дает правильный ответ. Жюри в недоумении и обращается к исходному тексту программы (правила предполагают, что на тестирование сдается исходный код, который компилируется на компиляторе командной строки и потом запускается на тестах). Недоразумение развеивается.

1. Что увидело жюри, открыв файл программы?

2. Какое решение имело в виду жюри?

Комменты пока скрываются.

Comments

[malyj-gorgan.livejournal.com]

Все что помню о простых числах -- определение. :) Исходя из этого, поскольку ограничений на размер исходника Вы не накладывали,

1. код программы -- определение массива из всех простых чисел меньше миллиона (итого 78948, исходник получается немногим больше полумега). Дальше понятно: считаем количество элементов между k и n.

2. а кто их знает? ;) Если разрешается в коде иметь массив 168 простых чисел меньше тысячи (если не разрешается, придется при исполнении генерировать массив простых чисел меньше/равно корню из n, что увеличит время на соответствующее, но несмертельное число операций). Дальше остается перебор. Если не умничать, и напрямую пропускать при переборе только четные числа, то получается максимум n / 2 * 167 целочисленных операций mod(). Самую малость меньше, учитывая, что простые числа до тысячи (или корня n) уже и так известны. Такой порядок алгоритма (<10^8) проходит ограничение по времени?