413 : 一人っ子数

dd桁の正の数(先行ゼロを持たない)がddで割り切れる部分文字列を一つだけ持つとき、その数を一人っ子数と呼ぼう。

例えば、5671は4桁の一人っ子数である。すべての部分文字列 5, 6, 7, 1, 56, 67, 71, 567, 671, 5671 のうち、56のみが4で割り切れる。 同様に、104 は 3 桁の一人っ子数、0 は 3 で割り切れるからである。 1132451 は 7 桁の一人っ子数、245 は 7 で割り切れるからである。

NN未満の一人っ子数の個数をF(N)F(N)としよう。 F(10)=9F(10) = 9, F(103)=389F(10^3) = 389, F(107)=277674F(10^7) = 277674であることが確かめられている。

F(1019)F(10^{19})を求めよ。

最終更新