YAPTCHA#5730

YAPTCHA (Həll təhlili)

Tutaq ki, $m = 3 k + 7$ m = 3k + 7. Onda tələb olunan ifadə aşağıdakı kimi yenidən yazıla bilər:

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,

Vilson teoremi. Əgər $m$ sadə ədəddirsə, onda

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

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

Yəni

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

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

Buna görə də, əgər $m$ sadə ədəddirsə, onda $\frac{( m - 1 )! + 1}{m}$ \frac{(m-1)!+1}{m} tam ədəd olacaq.

Eyni zamanda

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

Onda bütün ifadə bərabərdir

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

Əgər $m$ tərkib ədəddirsə, onda

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

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

çünki soldakı vurğunlar arasında $m$ ədədinin bütün bölənləri mövcuddur.

Bu halda

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

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

ifadəsi tam olacaq.

Onda bütün ifadə bərabərdir

⌊ \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-i hesablamaq üçün $1 \leq k \leq n$ 1 \le k \le n şərtini ödəyən $3 k + 7$ 3k + 7 formasında olan sadə ədədlərin sayını tapmaq kifayətdir.

Eratosthenes süzgəci vasitəsilə $u se d$ adlı bir massiv qururuq, burada:

u se d [i] = {1, 0, əgər i sadə ədəddirsə, əgər i tərkib ədəddirsə .

used[i] = \begin{cases} 1, & \text{əgər } i \text{ sadə ədəddirsə}, \\ 0, & \text{əgər } i \text{ tərkib ədəddirsə}. \end{cases}

Daha sonra $u se d$ massivindən istifadə edərək $3 i + 7$ 3i + 7 formasında olan sadə ədədləri təmsil edən $a$ massivini qururuq:

a [i] = {1, 0, əgər 3 i + 7 sadə ədəddirsə, əgər 3 i + 7 tərkib ədəddirsə .

a[i] = \begin{cases} 1, & \text{əgər } 3i + 7 \text{ sadə ədəddirsə}, \\ 0, & \text{əgər } 3i + 7 \text{ tərkib ədəddirsə}. \end{cases}

İndi

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

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

Çoxlu testlər olduğuna görə, onlara sabit vaxtda cavab vermək üçün prefiks cəmləri qururuq:

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

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

İndi hər $n$ dəyəri üçün sadəcə $p [n]$ -i çıxarmalıyıq.

Nümunə

Tutaq ki, $m = 7$ m = 7 — sadə. Onda

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

Tutaq ki, $m = 6$ m = 6 — tərkib. Onda

⌊ \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 üçün cavabı hesablayın. $3 k + 7$ 3k + 7 formasında olan bütün ədədləri nəzərdən keçirək, burada $1 \leq k \leq 10$ 1 \le k \le 10. Onlar arasında sadə ədədləri seçin.

Göstərilən ədədlər arasında $4$ sadə ədəd var: $13, 19, 31$ və $37$ . Deməli, $S_{10} = 4$ S_{10} = 4.

Alqoritmin implementasiyası

İş massivlərini elan edək. Çünki $n \leq 1 0^{6}$ n \le 10^6, massivlərin ölçüsünü $3 n + 7 = 3 \cdot 1 0^{6} + 7$ 3n + 7 = 3 \cdot 10^6 + 7 olaraq təyin etmək lazımdır.

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

Init funksiyası Eratosthenes süzgəcini həyata keçirir. $u se d$ massivi sadə ədədlər haqqında məlumatları saxlayır:

u se d [i] = {1, 0, əgər i sadə ədəddirsə, əgər i tərkib ədəddirsə .

used[i] = \begin{cases} 1, & \text{əgər } i \text{ sadə ədəddirsə}, \\ 0, & \text{əgər } i \text{ tərkib ədəddirsə}. \end{cases}

$a$ massivi $3 i + 7$ 3i + 7 formasında olan sadə ədədləri saxlayır:

a [i] = {1, 0, əgər 3 i + 7 sadə ədəddirsə, əgər 3 i + 7 tərkib ədəddirsə .

a[i] = \begin{cases} 1, & \text{əgər } 3i + 7 \text{ sadə ədəddirsə}, \\ 0, & \text{əgər } 3i + 7 \text{ tərkib ədəddirsə}. \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++

Proqramın əsas hissəsi. Massivləri doldururuq.

Init();

$a$ massivi üçün prefiks cəmlərini hesablamaq:

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$ sayda testləri ardıcıl işləyirik.

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

Hər $n$ dəyəri üçün $p [n]$ -i çıxarırıq.

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