三角数
Atcoderの過去問をぽちぽち解いているのですが、ARC129-C "Multiple of 7"は三角数の有名な性質を知っていたので気持ちよく解けました。
問題としては、任意の連続部分列を取ったときに7の倍数になるような場合がn通りあるような1~9の数字列を一つ構成せよということですね。
まず、7が単にm個並んでいる数字列を考えましょう。このとき、どこからどこまで区切っても、明らかに7の倍数です。よって、m(m+1)/2通り7の倍数になる区切り方があります。
このm(m+1)/2はm個のものから2個選ぶ場合の数ですが、三角数とも呼ばれています。
三角数には、以下の定理があります。
この定理を使って、問題を解けないか考えてみましょう。
i番目の三角数をt[i]とします。今n=t[i]+t[j]+t[k]と表せたとしましょう。このとき、"777…77177...77177...77"という数字列を考えます。ここで、最初は7がi個、次は7がj個、最後は7がk個並んでいます。1で区切られた各区間、任意の切り出し方をして得られた数字列は7しか含まないので、必ず7の倍数になります。これはt[i]+t[j]+t[k] = n通りあります。従って、ほかに7の倍数となる切り出し方がなければいいです。このとき、1を一つだけ含む切り出し方は明らかに7の倍数になりません。なので、1を二つ含む区間が7の倍数になるかを考えます。
よく知られていることとして、1001は7の倍数です。また、999999=1001×999も7の倍数です。
よって、1001×1000000-999999＝1000000001も7の倍数です。同様にして、1と1の間に0が6で割って2余る回数続く数は7の倍数です。逆にこれ以外は7の倍数にならないことも簡単にわかります。また100…001が7の倍数ならば、明らかにそれに1を足した100…002は7の倍数になりません。
よって、jが6で割って2余るならば、77…77177...77277...77を、それ以外なら77…77177...77177...77を出力するようにプログラムを組めばいいです。
三角数の数論的性質を使って解けたので、個人的に楽しい問題だと感じました。
