第19回日本情報オリンピック　二次予選

2019年12月12日
情報オリンピック日本委員会

解説

JOI 君が初めに持っていた可能性のある整数をN-到達数と呼ぶことにする．1 以上 N 以下の整数 x が N-到達数 である必要十分条件は下記の通りである：

• x=N または x+d(x) が N-到達数 となる．

ただし，d(x) は x を十進法で表したときの各桁の和である．

したがって，x=N,N-1,...,1 の順に N-到達数 であるかを判定すればよい．d(x) は O(log₁₀ N) で求めることができるので，全体の計算量は O(N log₁₀ N) となる．