5730. YAPTCHA

У математического факультета возникли проблемы. Из-за большого количества автоматизированных программ, просматривавших их веб-страницы, было принято решение ограничить доступ к научным статьям.

Теперь для получения доступа необходимо продемонстрировать свои знания – а именно решить математическую задачу.

Однако тест оказался слишком сложным не только для аспирантов, но даже для некоторых профессоров. Поэтому факультету требуется разработать программу, автоматически решающую эту задачу.

Посетителю главной страницы факультета математики предлагается следующая задача: по заданному натуральному числу n вычислить значение

S_n =

где ⌊x⌋ обозначает наибольшее целое число, не превосходящее x.

Вход. Первая строка содержит количество запросов t (t ≤ 10⁶).

Каждый из следующих t запросов содержит одно натуральное число  n (1 ≤ n ≤ 10⁶).

Выход. Для каждого запроса выведите в отдельной строке значение S_n.

Пример входа	Пример выхода
13 1 2 3 4 5 6 7 8 9 10 100 1000 10000	0 1 1 2 2 2 2 3 3 4 28 207 1609

РЕШЕНИЕ

решето Эратосфена

Анализ алгоритма

Пусть m = 3k + 7. Тогда искомое выражение перепишется в виде:

S_n =

Теорема Вильсона. Если m – простое число, то

(m – 1)! = -1 (mod m)

То есть

(m – 1)! + 1 = 0 (mod m)

Поэтому если m – простое число, то число будет целым.

В то же время

= = – 1

Тогда все выражение равно

= – = 1

Если m – составное число, то

(m – 1)! = 0 (mod m),

потому что среди множителей слева есть все делители числа m.

В этом случае число

будет целым.

Тогда все выражение равно

= = = 0

Для того чтобы вычислить S_n, достаточно посчитать количество простых чисел вида 3k + 7 при 1 ≤ k ≤ n.

При помощи решета Эратосфена строим массив used, в котором:

Далее используя массив used, строим массив a, который содержит информацию о простых числах вида 3i + 7:

Теперь

S_n = a[1] + a[2] + … + a[n]

Поскольку в задаче имеется много тестов, чтобы отвечать на них за константное время, построим префиксные суммы:

p[i] = a[1] + a[2] + … + a[i]

Теперь для ответа на задачу для кажого значения n достаточно вывести p[n].

Пример

Пусть m = 7 – простое. Тогда

= = = = 1

Пусть m = 6 – составное. Тогда

= = = = 0

Вычислим ответ для n = 10. Рассмотрим все числа вида 3k + 7, где 1 ≤ k ≤ 10. Выделим среди них простые.

Среди перечисленных чисел имеется 4 простых числа: 13, 19, 31 и 37. Следовательно, S₁₀ = 4.

Реализация алгоритма

Объявим рабочие массивы. Поскольку n ≤ 10⁶, размер массивов следует установить равным 3n + 7 = 3 * 10⁶ + 7.

#define MAX 3000010

char used[MAX], a[MAX];

Функция Init реализует решето Эратосфена. Массив used содержит информацию о простых числах:

Массив a содержит информацию о простых числах вида 3i + 7:

void Init()

{

for (int i = 2; i < MAX; i++)

{

if (!used[i])

{

if ((i - 7) % 3 == 0)

a[(i - 7) / 3] = true;

if (i < sqrt(MAX))

for (int j = i * i; j < MAX; j += i)

used[j] = true;

}

}

}

Основная часть программы. Заполняем массивы.

Init();

Вычисляем префиксные суммы для массива a:

p[i] = a₁ + a₂ + … + a_i

for (int i = 2; i < MAX; ++i)

p[i] = p[i - 1] + a[i];

Последовательно обрабатываем tests тестов.

scanf("%d", &tests);

while (tests--)

{

scanf("%d", &n);

Для каждого значения n выводим p[n].

printf("%d\n", p[n]);

}