(出題: noimi)

\(p\) 進数表記したときに、\(p-1\) が現れることと、整数が取り除かれることは同値です。

[証明]

帰納法による。 \(p -1\) が現れた数字が取り除かれることは、\(p-1\) の桁を \(0, \ldots, p -2\) に変えたものが等差数列をなす為、取り除かれる。

\(p-1\) が現れなかった数字は、\(p\) が素数であることからそれが末尾であるような長さ \(p\) の等差数列において必ず \(p-1\) が現れることが言える。

[証明終]

このような場合の数は桁 DP によって求めることができます。