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)\) 時間で解けるというわけではありません．
解答例
posted:
last update: