1182. Simple division

When performing integer division of a dividend n by a divisor d, we obtain a quotient q and a remainder r. The quotient q is the largest integer for which the inequality q · d ≤ n holds, and the remainder is given by r = n – q·d.

It is known that for any set of integers, there exists an integer d such that dividing each of these numbers by d yields the same remainder.

Input. Each line contains a sequence of 32-bit integers. The last number in each line is 0 and does not belong to the sequence. Each sequence contains at least 2 and at most 1000 numbers. It is guaranteed that not all numbers in a sequence are equal. The last line contains a single 0 and should not be processed.

Output. For each line, print the largest integer d such that dividing each number in the given sequence by d yields the same remainder.

Sample input	Sample output
701 1059 1417 2312 0 14 23 17 32 122 0 14 -22 17 -31 -124 0 0	179 3 3

SOLUTION

the greatest common divisor

Hint

1. Consider the second test case. What are the remainders when each number is divided by 3?

2. Consider the third test case. What are the remainders when each number is divided by 3? Recall how remainders are computed for negative numbers divided by positive numbers.

3. Let d be the largest number such that dividing all numbers a_i by d gives the same remainder. What can be said about the difference between any two numbers in the sequence with respect to d?

4. Represent the numbers a_i as a_i = d * r_i + rest and consider the differences a_i+1 – a_i. What is the largest possible value of d that satisfies these equalities? Recall the definition of the greatest common divisor.

Algorithm analysis

Let a sequence of numbers be given: a₁, a₂, …, a_k.

If, when dividing each number a_i (1 ≤ i ≤ k) by d, the remainder is the same, denote this remainder as rest. Then each number can be written in the form:

a₁ = d * r₁ + rest

a₂ = d * r₂ + rest

…

a_k = d * r_k + rest

Here r₁, r₂, …, rₖ are integers (the quotients of the divisions).

Now, subtract the consecutive elements of the sequence:

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

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

…

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

In all these differences, the number d is a factor. This means that d divides each of the differences: a₂ – a₁, a₃ – a₂, …, a_k – a_k-1.

We are looking for the largest possible d that divides all these differences. By definition, the largest number that divides several numbers simultaneously is their greatest common divisor (GCD). Therefore

d = GCD(|a₂ – a₁|, |a₃ – a₂|, …, |a_k – a_k-1|)

Since d is chosen to be maximal, the numbers r₂ − r₁, r₃ − r₂, … have no common divisor greater than 1. Otherwise, this common divisor could be factored out, increasing d, which would contradict its maximality. Therefore

GCD (r₁, r₂, …, r_n) = 1

Also note that if, for example, from each equation of the form a_i = d * r_i + rest (2 ≤ i ≤ k) we subtract the first one, then the answer can be written as:

d = GCD (|a₂ – a₁|, |a₃ – a₁|, …, |a_k – a₁|)

Sometimes, computations in this form are more convenient.

Example

For the first test case we have:

d = GCD(|1059 – 701|, |1417 – 1059|, |2312 – 1417|) = GCD(358, 358, 895) = 179

Algorithm implementation

The function gcd computes the greatest common divisor of two numbers a and b.

int gcd(int a, int b)

{

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

}

The main part of the program. Read the first number a₁. If it is 0, this means it is the last line and should not be processed – we exit the loop.

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

{

The variable res stores the current result – the greatest common divisor of the differences.

res = 0;

Read the next number of the line into the variable b. The result is computed using the formula

d = GCD(|a₂ – a₁|, |a₃ – a₁|, …, |a_k – a₁|)

In the code, the variable a stores the value of a₁, while the variable b takes the values a₂, a₃, …, a_k.

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

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

Print the answer.

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

}

Java implementation

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

}

}