Skip [AtCoder Beginner Contest 109 C]

atcoder.jp

数直線上において、初期座標 X と、目的地の座標が N 個与えられる。距離 D ずつしか移動できないとき、全ての目的地を訪れることのできる D のうち最大のものを求めよ、という問題です。

D=1 としてしまえば、あきらかに全ての目的地を訪れることができます。しかし D=2 のときは、たとえば初期座標が0で、目的地が1であった場合、どのように移動しても訪れることができません。

なんとなく、初期座標と各目的地の距離の絶対値の最大公約数が答えみたいだな、と思って提出したらどうやら正解だったようです。抽象的な思考が要求されていますね。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {

		int n = sc.nextInt();
		int k = sc.nextInt();
		int gcd = Math.abs(k - sc.nextInt());
		for (int i=1; i<n; i++) {
			gcd = gcd(gcd, Math.abs(k - sc.nextInt()));
		}
		System.out.println(gcd);

	}

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

}