Çoxluğu tap#5621

Çoxluğu tap (Həll təhlili)

Tutaq ki, $d_{1}, d_{2}, ..., d_{n}$ d_1, d_2, ..., d_n — giriş ədədləridir. Bu ədədlərin hamısının qismən cəmlərini nəzərdən keçirək

s_{i} = d_{1} + ... + d_{i}

s_i = d_1 + ... + d_i

Qismən cəmlərin sayı məhz $n$ olduğuna görə, bütün $s_{i} m o d n$ s_i~mod~n qiymətləri arasında ya iki bərabər, ya da ən az biri sıfıra bərabər olan bir dəyər mütləq tapılacaq.

Əgər bəzi indekslər üçün $a - 1 < b$ a - 1 < b şərti ödənirsə

s_{a - 1} m o d n = s_{b} m o d n,

s_{a-1}~mod~n = s_b~mod~n,

onda $d_{a} + ... + d_{b}$ d_a + ... + d_b cəmi $n$ -ə bölünür.

Nəticədə, $d_{a}, d_{a + 1}, ..., d_{b}$ d_a, d_{a + 1}, ..., d_b ədədlər ardıcıllığı axtarılan ardıcıllıqdır.

Əgər $i$ elədə bir $i$ mövcuddursa ki, $s_{i} m o d n = 0$ s_i~mod~n = 0, onda axtarılan ardıcıllıq $d_{1}, d_{2}, ..., d_{i}$ d_1, d_2, ..., d_i olacaqdır.

Nümunə

Gətirilmiş nümunəni nəzərdən keçirək. Bütün qismən cəmləri hesablayacağıq:

Axtarılan dəstlərdən bir neçə var. Məsələn:

çünki $s_{1} = s_{3}$ s_1 = s_3, onda $d_{2} + d_{3} = 5$ d_2 + d_3 = 5 $5$ -ə bölünür.
çünki $s_{1} = s_{5}$ s_1 = s_5, onda $d_{2} + d_{3} + d_{4} + d_{5} = 10$ d_2 + d_3 + d_4 + d_5 = 10 $5$ -ə bölünür.
çünki $s_{3} = s_{5}$ s_3 = s_5, onda $d_{4} + d_{5} = 5$ d_4 + d_5 = 5 $5$ -ə bölünür.
çünki $s_{4} = 0$ s_4 = 0, onda $d_{1} + d_{2} + d_{3} + d_{4} = 10$ d_1 + d_2 + d_3 + d_4 = 10 $5$ -ə bölünür.

Alqoritmin həyata keçirilməsi

Giriş ədədlərini $d$ massivində saxlayacağıq. Qismən cəmləri fiksasiya etmək üçün $r$ massivindən istifadə edəcəyik: əgər $s = d_{1} + ... + d_{i}$ s = d_1 + ... + d_i, onda $r [s] = i$ r[s] = i əmrini verəcəyik.

#define MAX 10100
int d[MAX], r[MAX];

Cəmləri $n$ -ə bölünən axtarılan ədədlər dəsti $d_{a}, d_{a + 1}, ..., d_{b}$ d_a, d_{a+1}, ..., d_b olacaq. Onların sayını $b - a + 1$ b - a + 1 çıxış edəcəyik, sonra isə ədədlərin özlərini hər sətirdə birini olmaqla verəcəyik.

void print(int a, int b)
{
  printf("%d\n",b - a + 1);
  for(int i = a; i <= b; i++)
    printf("%d\n",d[i]);
}

Proqramın əsas hissəsi. $r$ massivini $- 1$ ilə başla və ilk $i$ ədədlərinin cəmi $n$ -ə bölünəndə $r [0] = 0$ r[0] = 0 ayarla.

memset(r,-1,sizeof(r)); r[0] = 0;

Ədədlərin sayını $n$ oxuyuruq.

scanf("%d",&n);

Qismən cəmləri $n$ -ə modal olaraq $s u m$ dəyişənində hesablayırıq.

sum = 0;
for (i = 1; i <= n; i++)
{
  scanf("%d", &d[i]);
  sum = (sum + d[i]) % n;

Əgər qismən cəm $s u m$ təkrarlanarsa, axtarılan ədədlər dəstini çıxış edirik:

d_{r [s u m] + 1}, d_{r [s u m] + 2}, ..., d_{i}

d_{r[sum] + 1}, d_{r[sum] + 2}, ..., d_i

  if (r[sum] != -1)
  {
    print(r[sum] + 1, i);
    break;
  }

$r [s u m]$ $i$ ilk indeksini saxlayır, burada $d_{1} + ... + d_{i}$ d_1 + ... + d_i qismən cəmi $n$ -ə bölündükdə qalan $s u m$ olur.

  else r[sum] = i;
}