YAPTCHA#5730

YAPTCHA (Розбір)

Нехай $m = 3 k + 7$ m = 3k + 7. Тоді шуканий вираз перепишеться у вигляді:

S_{n} = m = 10, m = 1 (m o d 3) \sum 3 n + 7 ⌊ \frac{( m - 1 )! + 1}{m} - ⌊ \frac{( m - 1 )!}{m} ⌋ ⌋,

S_n = \sum_{m = 10, m = 1~(mod~3)}^{3n + 7} \left\lfloor \frac{(m - 1)! + 1}{m} - \left\lfloor \frac{(m - 1)!}{m} \right\rfloor \right\rfloor,

Теорема Вільсона. Якщо $m$ — просте число, то

(m - 1)! = - 1 (m o d m)

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

Тобто

(m - 1)! + 1 = 0 (m o d m)

(m - 1)! + 1 = 0~(mod~m)

Таким чином, якщо $m$ — просте число, то число $\frac{( m - 1 )! + 1}{m}$ \frac{(m-1)!+1}{m} буде цілим.

У той час

⌊ \frac{( m - 1 )!}{m} ⌋ = ⌊ \frac{( m - 1 )! + 1}{m} - \frac{1}{m} ⌋ = \frac{( m - 1 )! + 1}{m} - 1

\left\lfloor \frac{(m-1)!}{m} \right\rfloor = \left\lfloor \frac{(m - 1)! + 1}{m} - \frac{1}{m} \right\rfloor = \frac{(m - 1)! + 1}{m} - 1

Тоді весь вираз дорівнює

⌊ \frac{( m - 1 )! + 1}{m} - ⌊ \frac{( m - 1 )!}{m} ⌋ ⌋ = \frac{( m - 1 )! + 1}{m} - (\frac{( m - 1 )! + 1}{м} - 1) = 1

\left\lfloor \frac{(m - 1)! + 1}{m} - \left\lfloor \frac{(m - 1)!}{m} \right\rfloor \right\rfloor = \frac{(m - 1)! + 1}{m} - \left( \frac{(m - 1)! + 1}{м} - 1 \right) = 1

Якщо $m$ — складене число, то

(m - 1)! = 0 (m o d m),

(m - 1)! = 0~(mod~m),

оскільки серед множників зліва є всі дільники числа $m$ .

У цьому випадку число

\frac{( m - 1 )!}{m}

\frac{(m-1)!}{m}

буде цілим.

Тоді весь вираз дорівнює

⌊ \frac{( m - 1 )! + 1}{m} - ⌊ \frac{( m - 1 )!}{m} ⌋ ⌋ = ⌊ \frac{( m - 1 )!}{m} + \frac{1}{m} - \frac{( m - 1 )!}{m} ⌋ = ⌊ \frac{1}{m} ⌋ = 0

\left\lfloor \frac{(m - 1)! + 1}{m} - \left\lfloor \frac{(m - 1)!}{m} \right\rfloor \right\rfloor = \left\lfloor \frac{(m - 1)!}{m} + \frac{1}{m} - \frac{(m - 1)!}{m} \right\rfloor = \left\lfloor \frac{1}{m} \right\rfloor = 0

Щоб обчислити $S_{n}$ S_n, достатньо порахувати кількість простих чисел виду $3 k + 7$ 3k + 7 при $1 \leq k \leq n$ 1 \le k \le n.

За допомогою решета Ератосфена будуємо масив $u se d$ , в якому:

u se d [i] = {1, 0, якщо i просте, якщо i складене .

used[i] = \begin{cases} 1, & \text{якщо } i \text{ просте}, \\ 0, & \text{якщо } i \text{ складене}. \end{cases}

Далі, використовуючи масив $u se d$ , будуємо масив $a$ , який містить інформацію про прості числа виду $3 i + 7$ 3i + 7:

a [i] = {1, 0, якщо 3 i + 7 просте, якщо 3 i + 7 складене .

a[i] = \begin{cases} 1, & \text{якщо } 3i + 7 \text{ просте}, \\ 0, & \text{якщо } 3i + 7 \text{ складене}. \end{cases}

Тепер

S_{n} = a [1] + a [2] + \dots + a [n]

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

Оскільки в задачі є багато тестів, щоб відповідати на них за константний час, побудуємо префіксні суми:

p [i] = a [1] + a [2] + \dots + a [i]

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

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

Приклад

Нехай $m = 7$ m = 7 — просте. Тоді

⌊ \frac{6 ! + 1}{7} - ⌊ \frac{6 !}{7} ⌋ ⌋ = ⌊ \frac{721}{7} - ⌊ \frac{720}{7} ⌋ ⌋ = ⌊ 103 - ⌊ 102 \frac{6}{7} ⌋ ⌋ = ⌊ 103 - 102 ⌋ = 1

\left\lfloor \frac{6!+1}{7} - \left\lfloor \frac{6!}{7} \right\rfloor \right\rfloor = \left\lfloor \frac{721}{7} - \left\lfloor \frac{720}{7} \right\rfloor \right\rfloor = \left\lfloor 103 - \left\lfloor 102 \frac{6}{7} \right\rfloor \right\rfloor = \left\lfloor 103 - 102 \right\rfloor = 1

Нехай $m = 6$ m = 6 — складене. Тоді

⌊ \frac{5 ! + 1}{6} - ⌊ \frac{5 !}{6} ⌋ ⌋ = ⌊ \frac{121}{6} - ⌊ \frac{120}{6} ⌋ ⌋ = ⌊ 20 + \frac{1}{6} - 20 ⌋ = ⌊ \frac{1}{6} ⌋ = 0

\left\lfloor \frac{5!+1}{6} - \left\lfloor \frac{5!}{6} \right\rfloor \right\rfloor = \left\lfloor \frac{121}{6} - \left\lfloor \frac{120}{6} \right\rfloor \right\rfloor = \left\lfloor 20 + \frac{1}{6} - 20 \right\rfloor = \left\lfloor \frac{1}{6} \right\rfloor = 0

Обчислимо відповідь для $n = 10$ n = 10. Розглянемо всі числа виду $3 k + 7$ 3k + 7, де $1 \leq k \leq 10$ 1 \le k \le 10. Виділимо серед них прості.

Серед перелічених чисел є $4$ простих числа: $13, 19, 31$ та $37$ . Отже, $S_{10} = 4$ S_{10} = 4.

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

Оголосимо робочі масиви. Оскільки $n \leq 1 0^{6}$ n \le 10^6, розмір масивів слід встановити рівним $3 n + 7 = 3 \cdot 1 0^{6} + 7$ 3n + 7 = 3 \cdot 10^6 + 7.

#define MAX 3000010
char used[MAX], a[MAX];

Функція Init реалізує решето Ератосфена. Масив $u se d$ містить інформацію про прості числа:

u se d [i] = {1, 0, якщо i просте, якщо i складене .

used[i] = \begin{cases} 1, & \text{якщо } i \text{ просте}, \\ 0, & \text{якщо } i \text{ складене}. \end{cases}

Масив $a$ містить інформацію про прості числа виду $3 i + 7$ 3i + 7:

a [i] = {1, 0, якщо 3 i + 7 просте, якщо 3 i + 7 складене .

a[i] = \begin{cases} 1, & \text{якщо } 3i + 7 \text{ просте}, \\ 0, & \text{якщо } 3i + 7 \text{ складене}. \end{cases}

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;
    }
  }
}

C++

Основна частина програми. Заповнюємо масиви.

Init();

Обчислюємо префіксні суми для масиву $a$ :

p [i] = a_{1} + a_{2} + ... + a_{i}

p[i] = a_1 + a_2 + ... + a_i

for (int i = 2; i < MAX; ++i)
  p[i] = p[i - 1] + a[i];

Послідовно обробляємо $t es t s$ тестів.

scanf("%d", &tests);
while (tests--)
{
  scanf("%d", &n);

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

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