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

При делении числа n на d получается частное q и остаток r. При этом q – максимально возможное целое, для которого qd £ n, а r = n – qd. Для любого множества целых чисел {a₁, …, a_k} всегда существует такое d, что числа a_i mod d равны.

Вход. Каждая строка является отдельным тестом и содержит последовательность чисел a₁, …, a_k, заканчивающуюся нулем. Последний ноль не принадлежит самой последовательности. Последовательность содержит не менее 2 и не более 1000 чисел. Не все числа в последовательности равны между собой. Признаком конца входных данных является строка с одним нулем.

Выход. Для каждой входной последовательности a₁, …, a_k найти максимальное d, для которого при делении a_i на 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₁ = d * r₁ + rest

a₂ = d * r₂ + rest

…

a_k = d * r_k + rest

Поскольку d максимально , то НОД(r₁, r₂, …, r_n) = 1. Далее имеем:

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

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

…

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

Откуда d = НОД(|a₂ – a₁|, |a₃ – a₂|, …, |a_k – a_k-1|).

Пример

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

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

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

Функция gcd(int a, int b) вычисляет наибольший общий делитель двух чисел a и b.

int gcd(int a, int b)

{

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

}

Основной цикл программы состоит в чтении последовательности чисел {a₁, …, a_k} и последовательном вычислении значения НОД(|a₂ – a₁|, |a₃ – a₂|, …, |a_k – a_k-1|).

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

{

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

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

{

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

a = b;

}

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

}