1182. Simple division

Integer division between a dividend n and a divisor d yields a quotient q and a remainder r. q is the integer which maximizes q·d such that q·d ≤ n and r = n – q·d.

For any set of integers there is an integer d such that each of the given integers when divided by d leaves the same remainder.

Input. Each line contains a sequence of nonzero 32-bit signed integers separated by space. The last number on each line is 0 and this number does not belong to the sequence. There will be at least 2 and no more than 1000 numbers in a sequence; not all numbers occurring in a sequence are equal. The last line contains a single 0 and should not be processed.

Output. For each input line, print the largest integer which when divided into each of the input integers leaves 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. What are the remainders after the division of each number by 3?

2. Consider the third test. What are the remainders after the division of each number by 3? Remember how to calculate the remainders from division of negative integers by positive.

3. Let d is the maximum number, for which when we divide a_i by d, we get equal remainders. What can we say about the difference of any two numbers of the sequence with respect to d?

4. Represent the numbers a_i in the form a_i = d * r_i + rest and consider the differences a_i+1 – a_i. What is the maximum d that satisfies the given equations? Remember what is the greatest common divisor.

Algorithm analysis

From the problem statement implies that

a₁ = d * r₁ + rest

a₂ = d * r₂ + rest

…

a_k = d * r_k + rest

Since d is maximum, then GCD(r₁, r₂, …, r_n) = 1. Thus we have:

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

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

…

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

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

Example

For the first test case we have:

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

Algorithm realization

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

int gcd(int a, int b)

{

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

}

In the main part of the program read the sequence of numbers {a₁, …, a_k} and compute the value GCD(|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 realization

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

}

}