1182. Простое деление

При целочисленном делении делимого n на делитель d получаются частное q и остаток r. Частное q – это наибольшее целое число, для которого выполняется неравенство q·d ≤ n, а остаток равен r = n – q·d.

Известно, что для любого набора целых чисел существует такое целое число d, что при делении каждого из этих чисел на d получается один и тот же остаток.

Вход. Каждая строка содержит последовательность 32-битных знаковых целых чисел. Последнее число в каждой строке равно 0 и не входит в последовательность. В каждой последовательности содержится не менее 2 и не более 1000 чисел. Гарантируется, что не все числа в последовательности одинаковы. Последняя строка содержит число 0 и не обрабатывается.

Выход. Для каждой строки выведите наибольшее целое число d, такое что при делении каждого числа данной последовательности на d получается один и тот же остаток.

Пример входа	Пример выхода
701 1059 1417 2312 0 14 23 17 32 122 0 14 -22 17 -31 -124 0 0	179 3 3

РЕШЕНИЕ

наибольший общий делитель

Подсказка

1. Рассмотрите второй тест. Чему равны остатки при делении каждого числа на 3?

2. Рассмотрите третий тест. Чему равны остатки при делении каждого числа на 3? Вспомните, как вычисляются остатки при делении отрицательных чисел на положительные.

3. Пусть d – наибольшее число, для которого при делении всех чисел a_i на d получаются одинаковые остатки. Что можно сказать о разности любых двух чисел последовательности относительно числа d?

4. Представьте числа a_i в виде a_i = d * r_i + rest и рассмотрите разности a_i+1 – a_i. Какому наибольшему значению d удовлетворяют эти равенства? Вспомните определение наибольшего общего делителя.

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

Пусть дана последовательность чисел: a₁, a₂, …, a_k.

Если при делении каждого числа a_i (1 ≤ i ≤ k) на d остаток одинаков, обозначим этот остаток как rest. Тогда каждое число можно записать в виде:

a₁ = d * r₁ + rest

a₂ = d * r₂ + rest

…

a_k = d * r_k + rest

Здесь r₁, r₂, …, rₖ – целые числа (частные от деления).

Теперь вычтем соседние элементы последовательности:

a₂ – a₁ = d * (r₂ – r₁)

a₃ – a₂ = d * (r₃ – r₂)

…

a_k – a_k-1 = d * (r_k – r_k-1)

Во всех этих разностях число d является множителем. Значит, d делит каждую из разностей: a₂ – a₁, a₃ – a₂, …, a_k – a_k-1.

Мы ищем максимально возможное d, которое делит все эти разности. По определению, наибольшее число, делящее несколько чисел одновременно, – это их наибольший общий делитель (НОД). Следовательно

d = НОД(|a₂ – a₁|, |a₃ – a₂|, …, |a_k – a_k-1|)

Так как d выбрано максимальным, то числа r₂ − r₁, r₃ − r₂, … не имеют общего делителя больше 1. Иначе этот общий делитель можно было бы вынести, увеличив d, что противоречит его максимальности. Следовательно

НОД(r₁, r₂, …, r_n) = 1

Отметим также, что если, например, из каждого уравнения вида a_i = d * r_i + rest (2 ≤ i ≤ k) вычесть первое, то ответ можно записать в следующем виде:

d = НОД(|a₂ – a₁|, |a₃ – a₁|, …, |a_k – a₁|)

Иногда вычисления в таком виде являются более удобными.

Пример

Для первого теста получим:

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₁. Если оно рано 0, значит это последняя строка и она не обрабатывается – выходим из цикла.

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

{

Переменная res хранит текущий результат – наибольший общий делитель разностей.

res = 0;

Читаем очередное число строки в переменную b. Ответ вычисляем по формуле

d = НОД(|a₂ – a₁|, |a₃ – a₁|, …, |a_k – a₁|)

В коде переменная a хранит значение a₁, а переменная b принимает значения a₂, a₃, …, a_k.

while (scanf("%d", &b), b)

res = gcd(res, abs(b - a));

Выводим ответ.

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

}

Java реализация

import java.util.*;

public class Main

{

static int gcd(int a, int b)

{

return (b == 0) ? a : gcd(b, a % b);

}

public static void main(String []args)

{

Scanner con = new Scanner(System.in);

while(true)

{

int a = con.nextInt();

if (a == 0) break;

int b = con.nextInt();

int res = Math.abs(a - b);

a = b;

while(true)

{

b = con.nextInt();

if (b == 0) break;

res = gcd(res,Math.abs(a-b));

a = b;

}

System.out.println(res);

}

con.close();

}

}