483.最小好进制.md

解题关键点

• 符合最小好进制的数字 s，必须满足以下条件
  • 对于 n 进制和整数 m，有 1 + n + n ^ 2 + ... + n ^ m = s
  • 等式两边同时乘以 n，再相减，可以得到 s = (n ^ (m + 1) - 1) / (n - 1)
  • n 取最小可能值 2，可以得到 m 的最大值不会超过 log2(s - 1)
  • 循环 m 从最大值到 2，根据前面的等式可以得出 n 约等于 floor(s ^ (1 / m))，
  • 把 n 和 m 套入前面的等式验证即可

代码

impl Solution {
    pub fn smallest_good_base(s: String) -> String {
        let x: usize = s.parse::<usize>().unwrap();
        let mut m = (x as f64 - 1.0).log2().trunc();

        while m > 1.0 {
            let n = (x as f64).powf(1.0 / m) as usize;
            // 注意这里和解题关键点说的不一样，因为直接套公式会遇到丢失 f64 精度丢失的问题，所以改用最小好进制的规则逐位验证
            let mut y = x;
            while y % n == 1 {
                y /= n
            }
            if y == 0 {
                return n.to_string();
            }
            m -= 1.0;
        }

        // 最后直接返回当 m = 1.0 时的值即可。
        (x - 1).to_string()
    }
}

测试用例

assert_eq!(smallest_good_base("13".to_string()), "3");
assert_eq!(smallest_good_base("15".to_string()), "2");
assert_eq!(smallest_good_base("4681".to_string()), "8");
assert_eq!(smallest_good_base("1000000000000000000".to_string()), "999999999999999999");
assert_eq!(smallest_good_base("999999999999999999".to_string()), "999999999999999998");
assert_eq!(smallest_good_base("14919921443713777".to_string()), "496");