解説AC
ABCのこの問題のように類題は出題されています。しかし、このように逆に構成できることは思いつきませんでした。
右からi桁目までを10進数の整数としたとき、
なる区間(j,i]を10進数としたものが7の倍数となる条件は、
を満たすことです。なお、10と7は互いに素なので逆元を持つことが保証されます。
式を整理すると、
となるので、下から順にを計算して、余りがkとなるインデックスの個数をカウントします。
それをとすると、ここから2つ選ぶとその区間が表す10進数は7の倍数となるの
で、
となり、これをk=0〜6まで足すと、すべての組みが得られます。
今回はこれを逆に構成する問題でした。
公式解説のように高々7個ので解を構成できることにどうやったら気づけるか考えてみます。
構成部分以外の考え方は過去に出題例があるので、そこから当たりをつけて、実際に7回の操作でNを0にできるか、実装して確認してみるのが一案です。
もし、公式解説にある多角数定理を知っていれば、
を満たすa,b,cを求める問題になり、
以下の三角数は多くとも2000個は超えないので、
・予めi=1〜2000までの三角数を求めてハッシュマップなどに記録しておく
・a,bを全探索し、
を満たすcが存在するかハッシュマップで調べる
ことによって求めれるので、解を構成する余り3つをくらいの計算量で得られます。
ちなみにi文字目の求め方ですが、
をrとし、i文字目に整数xを設定し、
をdにしたいとします。
その時、
が成り立つので、
とすると、整数xを求められます。
公式解説通りの実装
多角数定理による実装