Решение

class Solution {
    fun climbStairs(n: Int): Int {
        fun fib(k: Int): Long {
            if (k == 0) return 0
            var a = 0L
            var b = 1L
            var bit = 31
            while (bit >= 0 && ((k shr bit) and 1) == 0) bit--
            while (bit >= 0) {
                val d = a * (2 * b - a)
                val e = a * a + b * b
                a = d
                b = e
                if (((k shr bit) and 1) == 1) {
                    val c = a + b
                    a = b
                    b = c
                }
                bit--
            }
            return a
        }
        return fib(n + 1).toInt()
    }
}