ヒント → https://atcoder.jp/contests/arc149/editorial/4868

---

[1] 基本方針

正整数 \(1\leq d\leq 9\) および \(n\) に対して，\(d\) を \(n\) 個並べてできる整数を \(x(n, d)\) と書くことにします：

\[x(n, d) = \underbrace{dd\cdots dd}_{n}\]

本問題は，\(x(n, d)\) （\(1\leq n\leq N\), \(1\leq d\leq 9\)） と書ける整数のうち \(M\) の倍数であるものの最大値を求める問題です．\(x(n, d)\) は全部で \(9N\) 個しかないので，すべての \(x(n,d)\) に対して \(O(1)\) 時間の計算を行っても全体の時間計算量は \(O(N)\) になります．したがって，次のような解法が考えられそうです．

• すべての \((n, d)\) に対して \(x(n, d) \bmod M\) を計算する．
• \(x(n, d) \bmod M = 0\) であるような \(x(n,d)\) のうちで最大のものを求める．

このうち「最大のもの」の計算は簡単で，\(n\) が最大のもののうちで \(d\) が最大のものを選べばよいです．以下では，すべての \((n, d)\) に対して \(x(n, d) \bmod M\) を計算する方法を解説します．

---

[2] \(x(n,d) \bmod M\) の計算

\(x(n-1,d) \bmod M\) などを既知として、\(x(n,d)\bmod M\) を計算する方法を，\(2\) つ紹介します．これらの方法によって，求めるべき \(x(n,d)\bmod M\) 全体を合計 \(O(N)\) 時間で計算できます．

---

[2 - 1] \(x(n,d)\) の計算方法 (1)

\(x(n-1, d)\) が \(x(n,d)\) の接頭辞であることに注目すると，

\[x(n,d) = 10x(n-1,d) + d\]

が成り立つことが分かります．この式を用いて小さな \(n\) から順に計算することで，各 \(x(n,d)\bmod M\) がひとつあたり \(O(1)\) 時間で計算できます．

---

[2 - 2] \(x(n,d)\) の計算方法 (2)

\(x(n-1, d)\) が \(x(n,d)\) の接尾辞であることに注目すると，

\[x(n,d) = d\times 10^{n-1} + x(n-1,d)\]

が成り立つことが分かります．この式を用いる場合には \(10^{n-1}\bmod M\) の値が必要になりますが，この値も \(10^n = 10\times 10^{n-1}\) を用いて小さな \(n\) から順に計算していくと，各 \(x(n,d)\bmod M\) がひとつあたり \(O(1)\) 時間で計算できます．

---

[3] 発展

次のような手順によって，最大値を与える \((n,d)\) をより高速な計算量で求めることもできます．

• \(d\) を固定して考える．
• \(x(n,d)\) が \(M\) の倍数となる最小の正整数 \(n\) を求める．これは，\(x(n,d) = 10x(n-1,d) + d\) に注目すると ABC 270 問題G と同様に解ける．
• \(x(n,d)\) が \(M\) の倍数となる最小の正整数 \(n\) を \(n_0\) とするとき，「\(x(n,d)\) が \(M\) の倍数である」ことと「\(n\) が \(n_0\) の倍数である」ことが同値であることが証明できる．したがって，最大の \(n\) を求めるには \(N\) 以下の最大の \(n_0\) の倍数を求めればよく，これは \(O(1)\) 時間でできる．

この方法によって期待計算時間 \(O(\sqrt{N})\) などで最適な \((n,d)\) を求めることができます．また，高速な素因数分解と \(x(n,d) = d\cdot \frac{10^n-1}{9}\)，Euler の定理などを用いてより高速に最適な \((n,d)\) を求めることも可能です．

ただし，本問では答の出力に \(\Omega(N)\) 時間かかるため，これらの解法でも \(o(N)\) 時間で解けるというわけではありません．

---

解答例

https://atcoder.jp/contests/arc149/submissions/35220937