\(N\) が \(2\) 桁の場合は簡単です。以下 \(N\) は \(k\ (3 \leq k)\) 桁の整数とします。

\(10^{k-1}-1=999...999\) は \(k-1\) 桁の整数であり、これは「周期的な数」です。よって \(N\) 以下の「周期的な数」を調べる際はこれと \(k\) 桁のものだけ調べればいいです。

\(k\) 桁の「周期的な数」\(n\) のうち、 \(a\) 桁の正整数 \(m\) を \(\frac{k}{a}\) 個結合して得られるようなものを考えます。 \(N\) の上 \(a\) 桁を整数として解釈した値を \(N'\) とすると \(m=N'-1\) のときは必ず \(n \leq N\) であり、\(m=N'+1\) のときは必ず \(N < n\) なので \(m=N'-1,\ N'\) だけ考えればいいです。

以上の考察で考えるべき「周期的な数」は \(O(\log {N})\) 個に絞り込めるので、 \(1\) ケース当たり \(O(\log^2 N)\) で解くことができます。

\(N'\) が \(10\) の累乗のときや、\(k\) 桁の「周期的な数」で \(N\) 以下のものが存在しないケースに注意しましょう。