Official

A - Repdigit Number Editorial by maspy


ヒント → 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

posted:
last update: