UVa 10407

From Algorithmist

Contents 1 10407 - Simple Division 2 Summary 3 Explanation 4 Gotchas 5 Notes 6 Input

[edit] 10407 - Simple Division

• http://acm.uva.es/p/v104/10407.html

[edit] Summary

An interesting problem in Number Theory.

[edit] Explanation

Let the list of positive integers be . We can rewrite the list as , where d_i is the difference between x_{i + 1} and x_i. Let m be a positive integer such that mod m. Then the first useful fact is that m can not be bigger than any d_i i=1..n-1. Otherwise, suppose that m > d_i for some i. Let mod m, i.e. x_i = km + r, r<m. Then x_{i + 1} = x_i + d_i = km + r + d_i. if r + d_i < m, then mod m. if , then mod m. Either way, mod m. Another important fact about m is that m has to divide all d_i's, i=2..n. Because mod m if and only if mod m. Combining the two facts, we know that the solution of the problem is the greatest common divisor of the d_i's, i=2..n.

[edit] Gotchas

• There may be duplicate integers in the input.

[edit] Notes

• In the proof, I am assuming that the integers are positive. But in the problem there may be some negative integers. But it seems that does not hurt the validity of the algorithm. Could anybody prove or disprove it?

[edit] Input

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

179
179
3
3