概要
どうも、灰色コーダーです。AtCoder Begginers Contest(ABC)のB問題もだいぶ解けるようになってきましたが、依然として解法が思いつかない問題が度々出てきます。それは整数を扱う問題です。私の中では、ABCのB問題で出てくる整数問題は、パターン・規則性の考察方法を知っていれば解けるというイメージですが、その考察方法を身につけるのが難しく苦しんでいます。というわけで、B埋め中に解けなかった整数問題を解いていきます。
問題
自分の考察
まず、問題は「Aの倍数を好きなように選んだ和をBで割った余りがCに一致しうるか」であるが、これを「Aの倍数をBで割った時の余りがCに一致しうるか」と置き換えることはできた。そして、Aの倍数をBで割った余りが 〜
をループするという規則性も見つけられた。しかしそれをコードに落とし込むことができなかった。
解法
A の倍数はいくつ足しても A の倍数であり、実は選ぶ数は 1 個だけで良い(いくつか選んで足さなくても、最終的な総和を直接Aの倍数から選べる)。次に、
という数列を考える。Aの倍数を考えるので自然な思考の流れである。ここで、
に注目すると、この数列は周期的で、最初の B 個の要素（ B 種類の余り）を繰り返す数列になっている。（ A を B で割った時の余りは必ず以下となることも忘れずに。）よって、この問題は
から
まで、愚直に B で割った余りを求めて調べれば良い。簡単な例で、AからBAまでの数列とその余りの例を示しておく。
見事に余りとして 〜
の間の数（B個の数）が繰り返されている。数の性質って綺麗だなあ。あとはこの余りの数列に
が含まれているかどうかを調べるだけ。
解法：C++でのコード
C++でのコードは以下の通り、
感想
本番で出たら思考停止してしまうような問題でした。余りの規則性が分かったのにも関わらず解法が思いつかないのは苦しいと思いました。整数の問題の思考方法というかどんな手順で問題を考察していけばいいのかがいまいち掴めていないです。精進あるのみですね。
もし整数問題の考察のコツ、これを参考にした方がいいなどありましたら、Twitterでリプいただけるとありがたいです。これでも見とけや！とリンク貼るだけでも大歓迎です。最後まで見ていただき本当にありがとうございました。
