YAPTCHA#5730

YAPTCHA (Editorial)

Let $m = 3 k + 7$ m = 3k + 7. Then the given expression can be rewritten in the form:

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,

Wilson's Theorem. If $m$ is a prime number, then

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

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

That is,

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

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

Therefore, if $m$ is prime, the number $\frac{( m - 1 )! + 1}{m}$ \frac{(m-1)!+1}{m} is an integer.

At the same time,

⌊ \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

Then the entire expression equals

⌊ \frac{( m - 1 )! + 1}{m} - ⌊ \frac{( m - 1 )!}{m} ⌋ ⌋ = \frac{( m - 1 )! + 1}{m} - (\frac{( m - 1 )! + 1}{m} - 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}{m} - 1 \right) = 1

If $m$ is a composite number, then

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

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

because among its factors there are all the divisors of $m$ .

In this case, the number

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

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

is an integer.

Then the entire expression equals

⌊ \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

Therefore, to compute $S_{n}$ S_n, it is enough to count the number of prime numbers of the form $3 k + 7$ 3k + 7 for $1 \leq k \leq n$ 1 \le k \le n.

Using the Sieve of Eratosthenes, we build the array $u se d$ , where:

u se d [i] = {1, 0, if i is prime, if i is composite .

used[i] = \begin{cases} 1, & \text{if } i \text{ is prime}, \\ 0, & \text{if } i \text{ is composite}. \end{cases}

Then, using the array $u se d$ , construct the array $a$ , which stores information about prime numbers of the form $3 i + 7$ 3i + 7:

a [i] = {1, 0, if 3 i + 7 is prime, if 3 i + 7 is composite .

a[i] = \begin{cases} 1, & \text{if } 3i + 7 \text{ is prime}, \\ 0, & \text{if } 3i + 7 \text{ is composite}. \end{cases}

Now

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

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

Since the problem contains many test cases, to answer each in constant time, we build the prefix sums:

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

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

Now, to solve the problem for any given value of $n$ , it is enough to print $p [n]$ .

Example

Let $m = 7$ m = 7 be a prime number. Then

⌊ \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

Let $m = 6$ m = 6 be a composite number. Then

⌊ \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

Let's compute the answer for $n = 10$ n = 10. Consider all numbers of the form $3 k + 7$ 3k + 7, where $1 \leq k \leq 10$ 1 \le k \le 10. Among them, identify the prime numbers.

Among the listed numbers, there are $4$ prime numbers: $13, 19, 31$ and $37$ . Therefore, $S_{10} = 4$ S_{10} = 4.

Algorithm implementation

Let us declare the arrays. Since $n \leq 1 0^{6}$ n \le 10^6, the size of the arrays should be set to $3 n + 7 = 3 \cdot 1 0^{6} + 7$ 3n + 7 = 3 \cdot 10^6 + 7.

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

The function Init implements the Sieve of Eratosthenes. The array $u se d$ stores information about prime numbers:

u se d [i] = {1, 0, if i is prime, if i is composite .

used[i] = \begin{cases} 1, & \text{if } i \text{ is prime}, \\ 0, & \text{if } i \text{ is composite}. \end{cases}

The array $a$ stores information about prime numbers of the form $3 i + 7$ 3i + 7:

a [i] = {1, 0, if 3 i + 7 is prime, if 3 i + 7 is composite .

a[i] = \begin{cases} 1, & \text{if } 3i + 7 \text{ is prime}, \\ 0, & \text{if } 3i + 7 \text{ is composite}. \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++

The main part of the program. Fill the arrays.

Init();

Compute the prefix sums for the array $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];

Process the tests sequentially.

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

For each value of $n$ print $p [n]$ .

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