Знайти кратне#5621

Знайти кратне (Розбір)

Нехай $d_{1}, d_{2}, ..., d_{n}$ d_1, d_2, ..., d_n — вхідні числа. Розглянемо всі їх часткові суми

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

s_i = d_1 + ... + d_i

Оскільки часткових сум рівно $n$ , то серед усіх значень $s_{i} m o d n$ s_i~mod~n обов’язково знайдуться або два однакових, або хоча б одне значення, рівне нулю.

Якщо для деяких індексів $a - 1 < b$ a - 1 < b виконується

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

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

то сума $d_{a} + ... + d_{b}$ d_a + ... + d_b ділиться на $n$ .

Отже, послідовність чисел $d_{a}, d_{a + 1}, ..., d_{b}$ d_a, d_{a + 1}, ..., d_b є шуканою.

Якщо ж існує таке $i$ , що $s_{i} m o d n = 0$ s_i~mod~n = 0, то шуканою буде послідовність $d_{1}, d_{2}, ..., d_{i}$ d_1, d_2, ..., d_i.

Приклад

Розглянемо наведений приклад. Обчислимо всі часткові суми:

Шуканих наборів є декілька. Наприклад:

оскільки $s_{1} = s_{3}$ s_1 = s_3, то $d_{2} + d_{3} = 5$ d_2 + d_3 = 5 ділиться на $5$ .
оскільки $s_{1} = s_{5}$ s_1 = s_5, то $d_{2} + d_{3} + d_{4} + d_{5} = 10$ d_2 + d_3 + d_4 + d_5 = 10 ділиться на $5$ .
оскільки $s_{3} = s_{5}$ s_3 = s_5, то $d_{4} + d_{5} = 5$ d_4 + d_5 = 5 ділиться на $5$ .
оскільки $s_{4} = 0$ s_4 = 0, то $d_{1} + d_{2} + d_{3} + d_{4} = 10$ d_1 + d_2 + d_3 + d_4 = 10 ділиться на $5$ .

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

Вхідні числа будемо зберігати в масиві $d$ . Масив $r$ використовуємо для фіксації часткових сум: якщо $s = d_{1} + ... + d_{i}$ s = d_1 + ... + d_i, то присвоїмо $r [s] = i$ r[s] = i.

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

Шуканим набором чисел, сума яких ділиться на $n$ , будуть $d_{a}, d_{a + 1}, ..., d_{b}$ d_a, d_{a+1}, ..., d_b. Виводимо їхню кількість $b - a + 1$ b - a + 1, а потім самі числа — по одному на кожному рядку.

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

Основна частина програми. Ініціалізуємо масив $r$ значенням $- 1$ і встановлюємо $r [0] = 0$ r[0] = 0, щоб врахувати випадок, коли сума перших $i$ чисел ділиться на $n$ .

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

Читаємо кількість чисел $n$ .

scanf("%d",&n);

Часткові суми за модулем $n$ обчислюємо в змінній $s u m$ .

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

Якщо часткова сума $s u m$ зустрілась повторно, то виводимо шуканий набір чисел:

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$ , на якому зустрілася часткова сума $d_{1} + ... + d_{i}$ d_1 + ... + d_i з залишком $s u m$ при діленні на $n$ .

  else r[sum] = i;
}