今回はユークリッド互除法の問題を解いてみました。

結果

f:id:c_taquna:20190826200750p:plain

コード

ユークリッド互除法は、2つの自然数の最大公約数を求めることができます。3つ以上の自然数の場合は、”AとBの最大公約数とCの最大公約数を計算する”ことで求めることができます。

今回は数直線状にある都市を全部回る必要があります。条件は下記。

スタート地点は X 現在の座標からDだけ移動することができる *全部の都市をまわる必要がある

このDを求めるのが今回の問題です。つまり、今の座標から全部の街をまわれる最大のDを計算します。

スタート地点のXから目標座標までの距離を計算します。Dだけ移動できるので、計算した距離をちょうど0にするには、距離の値がDの倍数である必要があります。つまり、このDは各地点までの距離の最大公約数を計算することで求められます。

これで距離を求めます。

for (long i = 0; i < N; i++)
{
    dist[i] = Math.Abs(X - long.Parse(input[i]));
}

これで、最大公約数を求めます。

static long CalGcd(long x, long y)
{
    if (y == 0) { return x; }
    return CalGcd(y, x % y);
}

ちょっとハマったポイントとしては、このように計算結果をgcdに入れないと、次のループ時にgcdが最初の2値の最大公約数とならず(初期値のまま)、NGになります。

for (long i = 0; i < N; i++)
{
    gcd = CalGcd(gcd, dist[i]);
}

わかりやすかったので、練習問題に良い