N=9N=9 のとき候補となる整数が 9×1089 \times 10^8 個あるため、愚直処理だと2秒以内に答えが出るかどうか怪しいです。 そこで、2秒以内で処理できるように候補の枝刈りを考えます。 X(X1)0(mod10N)X(X-1) \equiv 0 \pmod {10^N} なので 10N10^N を素因数分解して考えると「XXX1X-12N2^N または 5N5^N の倍数でなければならない」ということに気づけます。 59=19531255^9=1953125 なので 5N5^N の倍数だけ調べるようにすれば、2秒以内に余裕を持って処理することが出来ます。

別解として N=9N=9 程度なら事前に愚直に計算しておき解を埋め込むことでACすることも出来ます。 また、dfsなどの工夫をすると100桁くらいでも答えを得ることが出来ます。