$$1 \sim k , e.g., 5 \to (1,-1,-1)_3 \to (1, 1, 1, 1 \dots 1, 1 ) \to 1 + 3 ^ 1 + 3 ^ 2 + 3 ^ 3 \dots + 3 ^ k \to \frac{3^k - 1} { 2} \to 3^k \text{quick pow} \to O(\log n) $$