足跡-sokuseki-

りかの日進月歩の記録

AGC018 A Getting Difference

数学的な問題ほど解けないの、どうすればいいんでしょう…?
(解説を読んだ後、フォロワーさんたちにもいろいろ教えていただいた)

A - Getting Difference

問題概要

箱に  N 個のボールが入っていて、  i 番目のボールには整数  A_i が書かれている。
「箱から2つのボールを取り出し、その2つのボールに書かれている整数の差の絶対値を書いた新しいボールとともに箱に戻す」という操作を好きな回数行うことができる。
整数  K が書かれたボールが、箱の中に入っている状態にできるかどうかを判定する。

制約
 1 \le N \le 10^5
 1 \le A_i \le 10^9
 1 \le K \le 10^9

解法

(自分が理解したとおりに書いているので冗長でわかりにくいかも)

 M = max \{ A_i \} とする。

 M < K のときは不可能であることは明らかなので、  K \le M の場合を考える 。

 G = gcd \{ A_i \} とする。

 M  A_i のうちのどれかなので、 M  G の倍数である。

 K  G の倍数ならば、 M から  G を繰り返し引けば、かならず  K ができるので、 G が書かれたボールを作れればよい。

 G が書かれたボールがどんなときでも作れるのは互除法の考え方からわかる*1


また、 K  G の倍数でないなら、 K の書かれたボールはつくることはできない(  A_i はすべて  G の倍数であり、  G の倍数同士の差は必ず  G の倍数になる) 。



よって、この問題は

  •  K  A_i の最大値以下であるか
  •  K  A_i のgcdで割り切れるか

の2点を確かめさえすれば良い

Submission #1967366 - AtCoder Grand Contest 018

*1:2つの整数  x, y ( x > y とする) の差を繰り返し計算していくと、整数  x \% y ( = r )(  x  y で割ったあまり ) を作ることができる。つぎに  y, r の差を繰り返し計算していくと、整数  y \% r を作ることができる。これらの操作はユークリッドの互除法と同じで、最終的には  x, y のgcdを求めることができる。 N 個の整数のgcdを求める操作は2個の整数のgcdを求める操作の繰り返しでできるので、この問題で与えられた操作を使って、 A_i のgcdが書かれたボールを作ることができる