AtCoder Beginner Contest 156 F - Modularness

見てすぐに苦手な問題だと理解したけど、結果としては思いつけたし良かった。

https://atcoder.jp/contests/abc156/tasks/abc156_f

まず D の各項を M で割ったあまりに置き換える。ただし割り切れた場合は 0 ではなく M としておく。このようにしても答えは変わらない。このとき数列の値を数直線に描くと次のようになる。

f:id:pekempey:20200222230644p:plain

m の倍数をまたいだとき、次の項は前の項以下になり、そうでなければ次の項は前の項より大きくなる。つまり何回 m の倍数をまたいだかが分かれば答えがわかる。末項以下の m の倍数はすべてまたぐはずなので、末項を求めて m で割ればア≧イである個数は求められる。あとは全体からこれを引けば答えである。

はじめにさりげなく D の各項を M で割ったあまりに置き換えた。これは桁あふれなどの対策とは異なり、それ以上の重要な性質が得られている。