2022-03-23：在k进制下，最小多小的num，可以让1~num范围的数拥有1的个数不少于n个？

package main

import "fmt"

func main() {
  ret := minM(5, 2)
  fmt.Println(ret)
}

func minM(n, k int) int {
  len0 := bits(n, k)
  l := 1
  r := power(k, len0+1)
  ans := r
  for l <= r {
    m := l + ((r - l) >> 1)
    if ones(m, k) >= n {
      ans = m
      r = m - 1
    } else {
      l = m + 1
    }
  }
  return ans
}

func bits(num, k int) int {
  len0 := 0
  for num != 0 {
    len0++
    num /= k
  }
  return len0
}

func power(base, power int) int {
  ans := 1
  for power != 0 {
    if (power & 1) != 0 {
      ans *= base
    }
    base *= base
    power >>= 1
  }
  return ans
}

func ones(num, k int) int {
  len0 := bits(num, k)
  if len0 <= 1 {
    return len0
  }
  offset := power(k, len0-1)
  first := num / offset
  curOne := num%offset + 1
  if first != 1 {
    curOne = offset
  }
  restOne := first * (len0 - 1) * (offset / k)
  return curOne + restOne + ones(num%offset, k)
}