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

Результатом целочисленного деления делимого n и делителя d является частное q и остаток r. q является числом, которое максимизирует q·d, то есть q·d ≤ n и r = n – q·d.

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

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

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

Пример входа	Пример выхода
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(a, 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);

}

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();

}

}