[UVA10407]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 of input contains a sequence of nonzero integer numbers separated by a 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 occuring in a sequence are equal. The last line of input contains a single 0 and this line should not be processed.

Output

For each line of input, output the largest integer which when divided into each of the input integers leaves the same remainder.

Sample Input

701 1059 1417 2312 0 14 23 17 32 122 0 14 -22 17 -31 -124 0 0

Sample Output

179 3 3

題意: 找出一個最大除數使得所有數字都能有相同的餘數。由餘式定理可以推出如果每個數的餘數都要相同時，他們之間一定會有公因數，將兩兩數之差做過一輪GCD即可。

我的以往GCD寫法讓我錯了不少次…

int gcd(int a,int b) { 
  int temp = 0; 
  while(a % b) { 
    temp = b; 
    b = a % b; 
    a = temp; 
  }
  return b; 
}

這樣寫在b是非零的狀況下是可行的，但一但b等於零則會造成錯誤(跟0取餘數)。

以下兩種寫法則可以避免掉這種狀況:

int gcd(int a, int b) { 
  return b == 0 ? a : gcd( b, a % b ); 
}

int gcd(int a,int b) { 
  int temp = 0; 
  while(b != 0) { 
    temp = b; 
    b = a % b; 
    a = temp; 
  } 
  return a; 
}

#include <stdio.h> 
#include <stdlib.h> 
int gcd(int a,int b) { 
  int temp = 0; 
  while(b != 0) { 
    temp = b; 
    b = a % b; 
    a = temp; 
  } 
  return a; 
} 
int arr1[1005] = {0}; 
int div1[1005] = {0}; 
int main() { 
  while(scanf("%d",&arr1[0])) { 
    if(arr1[0] == 0) break; 
    int n = 1; 
    while(scanf("%d",&arr1[n])) { 
      if(arr1[n] == 0) break; 
      div1[n-1] = abs(arr1[n]-arr1[n-1]); n++; 
    } 
    int temp = div1[0]; 
    for(int i = 1 ; i < n-1 ; ++i) { 
      temp = gcd(temp,div1[i]); 
    } 
    printf("%d\n",temp); 
  } 
  return 0; 
}