UVa 10407

From Algorithmist
Jump to navigation Jump to search

10407 - Simple Division[edit]

Summary[edit]

An interesting problem in Number Theory.

Explanation[edit]

Let the list of positive integers be . We can rewrite the list as , where is the difference between and . Let m be a positive integer such that mod m.

Then the first useful fact is that m can not be bigger than any i=1..n-1. Otherwise, suppose that m > for some i. Let mod m, i.e. = km + r, r<m. Then . if , then mod m. if , then mod m. Either way, mod m.

Another important fact about m is that m has to divide all '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 's, i=2..n.

Gotchas[edit]

  • There may be duplicate integers in the input.

Notes[edit]

  • 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?

Implementations[edit]

Input[edit]

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