Google Code Jam 2010 Qualification B

Problem B: Fair Warning

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p1&a=1
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=1


這一題的題目很有趣, 但是解起來就不是那麼有趣了, 因為牽扯到大數的問題.
還好我是用JAVA解題, 內建就有大數的函式庫可以使用

題目是說, 在Jamcode星球上, 有一種預言, 西元前發生的幾件大事件, 會暗示哪一天是世界末日

例如:
西元前26000, 11000, 6000年發生了大事件, 則西元4000年會導致世界末日.
因為西元4000年, 離這三個事件分別是30000, 15000, 10000年, 都是5000的倍數, 並且, 5000是一個最大的因數

以這個例子來看
(26000+4000) % 5000 = (11000+4000) % 5000 
(11000+4000) % 5000 = (6000+4000) % 5000 
(26000-11000) % 5000 = 0
(11000-6000) % 5000 = 0

所以
(a + y) % T = (b + y) % T
(a - b) % T = 0

因此, 所有年份的相差值中, 去取出最大公因數, 就是解答