Простий поділ#1182

Простий поділ (Розбір)

Розгляньте другий тест. Чому рівні остачі при діленні кожного числа на $3$ ?
Розгляньте третій тест. Чому рівні остачі при діленні кожного числа на $3$ ? Згадайте, як обчислюються остачі при діленні від'ємних чисел на додатні.
Нехай $d$ — найбільше число, для якого при діленні всіх чисел $a_{i}$ a_i на $d$ отримуються однакові остачі. Що можна сказати про різницю будь-яких двох чисел послідовності відносно числа $d$ ?
Подайте числа $a_{i}$ a_i у вигляді $a_{i} = d \cdot r_{i} + r es t$ a_i = d \cdot r_i + rest і розгляньте різниці $a_{i + 1} - a_{i}$ a_{i+1} - a_i. Якому найбільшому значенню $d$ задовольняють ці рівняння? Згадайте визначення найбільшого спільного дільника.

Аналіз алгоритму

Нехай дана послідовність чисел: $a_{1}, a_{2}, ..., a_{k}$ a_1, a_2, ..., a_k.

Якщо при діленні кожного числа $a_{i} (1 \leq i \leq k)$ a_i~(1 \le i \le k) на $d$ остача однакова, позначимо цю остачу як $r es t$ . Тоді кожне число можна записати у вигляді:

a_{1} = d \cdot r_{1} + r es t a_{2} = d \cdot r_{2} + r es t ... a_{k} = d \cdot r_{k} + r es t

a_1 = d \cdot r_1 + rest \\ a_2 = d \cdot r_2 + rest \\ ... \\ a_k = d \cdot r_k + rest

Тут $r_{1}, r_{2}, ..., r_{k}$ r_1, r_2, ..., r_k — цілі числа (частки від ділення).

Тепер вирахуємо сусідні елементи послідовності:

a_{2} - a_{1} = d \cdot (r_{2} - r_{1}) a_{3} - a_{2} = d \cdot (r_{3} - r_{2}) ... a_{k} - a_{k - 1} = d \cdot (r_{k} - r_{k - 1})

a_2 - a_1 = d \cdot (r_2 - r_1) \\ a_3 - a_2 = d \cdot (r_3 - r_2) \\ ... \\ a_k - a_{k-1} = d \cdot (r_k - r_{k-1})

У всіх цих різницях число $d$ є множником. Значить, $d$ ділить кожну з різниць: $a_{2} - a_{1}, a_{3} - a_{2}, ..., a_{k} - a_{k - 1}$ a_2 - a_1, a_3 - a_2, ..., a_k - a_{k-1}.

Ми шукаємо максимальне можливе $d$ , що ділить всі ці різниці. За визначенням, найбільше число, що ділить кілька чисел одночасно, — це їх найбільший спільний дільник (НСД). Отже

d = НСД (∣ a_{2} - a_{1} ∣, ∣ a_{3} - a_{2} ∣, ..., ∣ a_{k} - a_{k - 1} ∣)

d = НСД(|a_2 - a_1|, |a_3 - a_2|, ..., |a_k - a_{k-1}|)

Оскільки $d$ вибрано максимальним, то числа $r_{2} - r_{1}, r_{3} - r_{2}, ...$ r_2 - r_1, r_3 - r_2, ... не мають спільного дільника більше $1$ . Інакше цей спільний дільник можна було б винести, збільшивши $d$ , що суперечить його максимальності. Таким чином

НСД (r_{1}, r_{2}, ..., r_{n}) = 1

НСД(r_1, r_2, ..., r_n) = 1

Зазначимо також, що якщо, наприклад, з кожного рівняння виду $a_{i} = d \cdot r_{i} + r es t (2 \leq i \leq k)$ a_i = d \cdot r_i + rest~(2 \le i \le k) віднімемо перше, то відповідь можна записати у наступному вигляді:

d = НСД (∣ a_{2} - a_{1} ∣, ∣ a_{3} - a_{1} ∣, ..., ∣ a_{k} - a_{1} ∣)

d = НСД(|a_2 - a_1|, |a_3 - a_1|, ..., |a_k - a_1|)

Іноді обчислення в такому вигляді є більш зручними.

Приклад

Для першого тесту отримаємо:

d = НСД (∣1059 - 701∣, ∣1417 - 1059∣, ∣2312 - 1417∣) = НСД (358, 358, 895) = 179.

d = НСД(|1059 - 701|, |1417 - 1059|, |2312 - 1417|) = НСД(358, 358, 895) = 179.

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

Функція gcd обчислює найбільший спільний дільник двох чисел $a$ і $b$ .

int gcd(int a, int b)
{
  return (!b) ? a : gcd(b, a % b);
}

Основна частина програми. Читаємо перше число $a_{1}$ a_1. Якщо воно дорівнює $0$ , значить це останній рядок і він не обробляється — виходимо з циклу.

while (scanf("%d", &a), a)
{

Змінна $r es$ зберігає поточний результат — найбільший спільний дільник різниць.

  res = 0;

Читаємо чергове число рядка у змінну $b$ . Відповідь обчислюємо за формулою

d = НСД (∣ a_{2} - a_{1} ∣, ∣ a_{3} - a_{1} ∣, ..., ∣ a_{k} - a_{1} ∣)

d = НСД(|a_2 - a_1|, |a_3 - a_1|, ..., |a_k - a_1|)

У коді змінна $a$ зберігає значення $a_{1}$ a_1, а змінна $b$ приймає значення $a_{2}, a_{3}, ..., a_{k}$ a_2, a_3, ..., a_k.

  while (scanf("%d", &b), b)
    res = gcd(res, abs(b - a));

Виводимо відповідь.

  printf("%d\n", res);
}