Note that when \(N=a \times 2^b + c\) and \(N \leq 10^{18}\), we only need to consider \(60\) values for \(b\): from \(0\) to \(59\). (If \(b \geq 60\) and \(N=a \times 2^b + c\), \(a\) must be \(0\), so we can change \(b\) to \(0\) while still satisfying \(N=a \times 2^b + c\).) We can try all of them and let \(a = \lfloor N \div 2^b \rfloor, c = N - \lfloor N \div 2^b \rfloor \times 2^b\) to minimize \(a + b + c\) for each of those values to find the minimum possible value of \(a + b + c\).

Sample Implementations

• C++: https://atcoder.jp/contests/arc119/submissions/22625401
• Python: https://atcoder.jp/contests/arc119/submissions/22629725
• Java: https://atcoder.jp/contests/arc119/submissions/22631998
• C: https://atcoder.jp/contests/arc119/submissions/22632583