Maximize number of nice divisors

Math Recursion Number Theory

35.4% acceptance

Feb 25, 2026

233

171

You are given a positive integer primeFactors. You are asked to construct a positive integer n that satisfies the following conditions: The number of prime factors of n (not necessarily distinct) is at most primeFactors. The number of nice divisors of n is maximized. Note that a divisor of n is nice if it is divisible by every prime factor of n. Return the number of nice divisors of n. Since that number can be too large, return it modulo 10^9 + 7. Note that a prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_nice_divisors(prime_factors: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = prime_factors as i64;
    if n == 1 { return 1; }
    if n == 2 { return 2; }
    if n == 3 { return 3; }

    fn pow_mod(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
      let mut result = 1i64;
      base %= modulus;
      while exp > 0 {
        if exp & 1 == 1 {
          result = result * base % modulus;
        }
        base = base * base % modulus;
        exp >>= 1;
      }
      result
    }

    let res = match n % 3 {
      0 => pow_mod(3, n / 3, MOD),
      1 => pow_mod(3, n / 3 - 1, MOD) * 4 % MOD,
      _ => pow_mod(3, n / 3, MOD) * 2 % MOD,
    };
    res as i32
  }
}