Simple division#1182

Simple division (Editorial)

Consider the second test case. What are the remainders when each number is divided by $3$ ?
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.
Let $d$ be the largest number such that dividing all numbers $a_{i}$ 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$ ?
Represent the numbers $a_{i}$ a_i as $a_{i} = d \cdot r_{i} + r es t$ a_i = d \cdot r_i + rest and consider the differences $a_{i + 1} - a_{i}$ 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_{1}, a_{2}, ..., a_{k}$ a_1, a_2, ..., a_k.

If, when dividing each number $a_{i} (1 \leq i \leq k)$ a_i~(1 \le i \le k) by $d$ , the remainder is the same, denote this remainder as $r es t$ . Then each number can be written in the form:

a_{1} = d \cdot r_{1} + r es t a_{2} = d \cdot r_{2} + r es t ... a_{k} = d \cdot r_{k} + r es t

a_1 = d \cdot r_1 + rest \\ a_2 = d \cdot r_2 + rest \\ ... \\ a_k = d \cdot r_k + rest

Here $r_{1}, r_{2}, ..., r_{k}$ r_1, r_2, ..., r_k are integers (the quotients of the divisions).

Now, subtract the consecutive elements of the sequence:

a_{2} - a_{1} = d \cdot (r_{2} - r_{1}) a_{3} - a_{2} = d \cdot (r_{3} - r_{2}) ... a_{k} - a_{k - 1} = d \cdot (r_{k} - r_{k - 1})

a_2 - a_1 = d \cdot (r_2 - r_1) \\ a_3 - a_2 = d \cdot (r_3 - r_2) \\ ... \\ a_k - a_{k-1} = d \cdot (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_{2} - a_{1}, a_{3} - a_{2}, ..., a_{k} - a_{k - 1}$ a_2 - a_1, a_3 - a_2, ..., 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 = GC D (∣ a_{2} - a_{1} ∣, ∣ a_{3} - a_{2} ∣, ..., ∣ a_{k} - a_{k - 1} ∣)

d = GCD(|a_2 - a_1|, |a_3 - a_2|, ..., |a_k - a_{k-1}|)

Since $d$ is chosen to be maximal, the numbers $r_{2} - r_{1}, r_{3} - r_{2}, ...$ r_2 - r_1, r_3 - r_2, ... have no common divisor greater than $1$ . Otherwise, this common divisor could be factored out, increasing $d$ , which would contradict its maximality. Therefore

GC D (r_{1}, r_{2}, ..., r_{n}) = 1

GCD(r_1, r_2, ..., r_n) = 1

Also note that if, for example, from each equation of the form $a_{i} = d \cdot r_{i} + r es t (2 \leq i \leq k)$ a_i = d \cdot r_i + rest~(2 \le i \le k) we subtract the first one, then the answer can be written as:

d = GC D (∣ a_{2} - a_{1} ∣, ∣ a_{3} - a_{1} ∣, ..., ∣ a_{k} - a_{1} ∣)

d = GCD(|a_2 - a_1|, |a_3 - a_1|, ..., |a_k - a_1|)

Sometimes, computations in this form are more convenient.

Example

For the first test case we have:

d = GC D (∣1059 - 701∣, ∣1417 - 1059∣, ∣2312 - 1417∣) = НОД (358, 358, 895) = 179.

d = GCD(|1059 - 701|, |1417 - 1059|, |2312 - 1417|) = НОД(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_{1}$ a_1. 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 $r es$ 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 = GC D (∣ a_{2} - a_{1} ∣, ∣ a_{3} - a_{1} ∣, ..., ∣ a_{k} - a_{1} ∣)

d = GCD(|a_2 - a_1|, |a_3 - a_1|, ..., |a_k - a_1|)

In the code, the variable $a$ stores the value of $a_{1}$ a_1, while the variable $b$ takes the values $a_{2}, a_{3}, ..., a_{k}$ a_2, a_3, ..., a_k.

  while (scanf("%d", &b), b)
    res = gcd(res, abs(b - a));

Print the answer.

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