k进制下一的个数

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return long长整型
     */
    public long minM (int n, int k) {
        // write code here
        int len = getBits(n, k);     // 计算n是几位数
        // k进制数的左右边界
        long left = 1;
        long right = (long)Math.pow(k, len + 1);
        // 二分法找最小的m
        long lowestM = right;
        while(left <= right){
            long m = left + ((right - left) >> 1);
            if(caculateOnes(m, k) < n){
                left = m + 1;
            }else{
                lowestM = m;
                right = m - 1;
            }
        }
        return lowestM;
    }
    
    // 计算k进制下1~m有多少个1
    private long caculateOnes(long num, int k) {
        int len = getBits(num, k);
        if(len <= 1){
            return len;
        }
        long offset = (long)Math.pow(k, len - 1);
        long first = num / offset;
        long curOne = first == 1 ? (num % offset) + 1 : offset;
        long restOne = first * (len - 1) * (offset / k);
        return curOne + restOne + caculateOnes(num % offset, k);
    }
    
    // 计算num有多少位
    private int getBits(long num, int radix) {
        int len = 0;
        while(num > 0){
            num /= radix;
            len++;
        }
        return len;
    }
}