[1] 足し算の繰り上がりと各桁の和

一般に、\(a+b\) の各桁の和 \(f(a+b)\) について次が成り立ちます：

\(a+b\) を筆算で計算する際の繰り上がりの回数を \(k\) とするとき，\(f(a+b) = f(a) + f(b) - 9k\) が成り立つ．

「繰り上がり」というのはある桁から \(10\) を引き，ひとつ上の桁の \(1\) を加える操作であることから分かります．

---

[2] \(M\) の決定

正整数 \(x\) が \(f(x)=N\) を満たすとします．\(x+x\) を筆算で計算する際の繰り上がりの回数を \(k\) とすると，[1] より \(f(2x)=f(x) + f(x) - 9k = 2N - 9k\) となります．

したがって，

• 必ず \(f(2x) \leq 2N\) が成り立つこと．
• \(x\) の全ての桁が \(4\) 以下であるとき，そのときに限り \(f(2x) = 2N\) が成り立つこと．

が分かります．\(f(x)=N\) かつ \(x\) の全ての桁が \(4\) 以下であるような \(x\) は存在する（例えば \(x = \underbrace{111\cdots 111}_{N}\)）ことから，\(M = 2N\) であることが分かります．

---

[3] \(x\) の決定

\(f(x)=N\) かつ \(f(2x) = 2N\) であるような最小の正整数 \(x\) を求めましょう．

そのような \(x\) について，次が成り立ちます．

• 全ての桁は \(4\) 以下である．
• 先頭の桁以外はすべて \(4\) である．

前者の条件は [2] で述べた通りです．

後者の条件を確かめましょう．\(x\) の先頭以外の桁で \(3\) 以下であるものが存在したとします．そのうち最も手前にある桁に注目します． その桁を \(1\) 増加させ，その手前の桁を \(1\) 減少させることにより，\(f(x)=N\) かつ \(f(2x)=2N\) という条件を保ったまま \(x\) を減少させることができます．これは \(x\) の最小性に矛盾します．

\(f(x) = N\) かつこれらの \(2\) 条件を満たす \(x\) はひとつしかありません．具体的には次の通りです．

• \(N = 4k\) のとき：\(x = \underbrace{44\cdots 44}_{k}\)
• \(N = 4k+1\) のとき：\(x = 1\underbrace{44\cdots 44}_{k}\)
• \(N = 4k+2\) のとき：\(x = 2\underbrace{44\cdots 44}_{k}\)
• \(N = 4k+3\) のとき：\(x = 3\underbrace{44\cdots 44}_{k}\)

これらの \(M, x\) を出力すると正答になります．出力に \(\Theta(N)\) 時間がかかり，計算量は \(\Theta(N)\) 時間となります．