在k进制下，最小多小的num，可以让1~num范围的数拥有1的个数不少于n个？
二分法。
代码用golang编写。代码如下：
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)
}执行结果如下：
