AGC018 A Getting Difference
数学的な問題ほど解けないの、どうすればいいんでしょう…?
(解説を読んだ後、フォロワーさんたちにもいろいろ教えていただいた)
問題概要
箱に 個のボールが入っていて、 番目のボールには整数 が書かれている。
「箱から2つのボールを取り出し、その2つのボールに書かれている整数の差の絶対値を書いた新しいボールとともに箱に戻す」という操作を好きな回数行うことができる。
整数 が書かれたボールが、箱の中に入っている状態にできるかどうかを判定する。
制約
解法
(自分が理解したとおりに書いているので冗長でわかりにくいかも)
とする。
のときは不可能であることは明らかなので、 の場合を考える 。
とする。
は のうちのどれかなので、 は の倍数である。
が の倍数ならば、 から を繰り返し引けば、かならず ができるので、 が書かれたボールを作れればよい。
が書かれたボールがどんなときでも作れるのは互除法の考え方からわかる*1。
また、 が の倍数でないなら、 の書かれたボールはつくることはできない( はすべて の倍数であり、 の倍数同士の差は必ず の倍数になる) 。
よって、この問題は
- が の最大値以下であるか
- が のgcdで割り切れるか
の2点を確かめさえすれば良い
*1:2つの整数 ( とする) の差を繰り返し計算していくと、整数 を で割ったあまり ) を作ることができる。つぎに の差を繰り返し計算していくと、整数 を作ることができる。これらの操作はユークリッドの互除法と同じで、最終的には のgcdを求めることができる。 個の整数のgcdを求める操作は2個の整数のgcdを求める操作の繰り返しでできるので、この問題で与えられた操作を使って、 のgcdが書かれたボールを作ることができる