No.491

$N \leq 10^{18}$ なので $10^9+1$ の倍数を $(10^9+1)k$ と表すと $k \leq 10^9-1$ である. よって倍数は下9桁が $k$ であり, 下9桁を除いた部分も $k$ となる.

これが回文数になるためには, $k$ も回文数である必要がある.

$k \leq m$ となる回文数の数を考える.

$n$ 桁の数字を考えると, その数字を反転させたものを末尾に付け足すことで $2n$ 桁の回文数が作れる. 同様にその数字の上位 $n-1$ 桁を反転させたものを末尾に付け足すことで $2n+1$ 桁の回文数を作れる.

よって, $m$ の桁数を $n$ とすると, $\lceil n/2 \rceil$ 桁までの数字すべてについて上記2種類の回文数を作ってみて, それぞれ $m$ 以下になるかどうかを確認する.

調べるのは高々 $10^5$ 以下の数になるので十分間に合う.