Google Code Jam Qualification 2010 B

紙で計算してみると、t1-t2, t2-t3, t(n-1) - t(n)のgcdをTとして、
t1+yがTの倍数となる最小のyを計算すればよさそうだが、数学的に証明ができない。
まあ、正解だったから、解説が出るまで待ってみよう。

public void run(String file) throws Exception {
Scanner scan = new Scanner(file);
int T = scan.nextInt();
for (int testcase = 0; testcase < T; testcase++) {
int N = scan.nextInt();
BigInteger[] ts = new BigInteger[N];
for (int i = 0; i < N; i++) {
ts[i] = new BigInteger(scan.next());
}
BigInteger[] ds = new BigInteger[N-1];
for (int i = 0; i < N-1;i++) {
ds[i] = ts[i+1].subtract(ts[i]).abs();
}
BigInteger gcd = ds[0];
for (int i =1; i < ds.length;i++) {
gcd = gcd.gcd(ds[i]);
}
//debug(ts, ts[0], gcd);
BigInteger ans = gcd.subtract(ts[0].mod(gcd)).mod(gcd);
write("Case #%d: %s\n", testcase+1, ans.toString());
}
}