Problem

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. For example, if n = 12, then its prime factors are [2,2,3], then 6 and 12 are nice divisors, while 3 and 4 are not.

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. The prime factors of a number n is a list of prime numbers such that their product equals n.

Examples

Example 1

1
2
3
4
5

Input: primeFactors = 5
Output: 6
Explanation: 200 is a valid value of n.
It has 5 prime factors: [2,2,2,5,5], and it has 6 nice divisors: [10,20,40,50,100,200].
There is not other value of n that has at most 5 prime factors and more nice divisors.

Example 2

1
2

Input: primeFactors = 8
Output: 18

Constraints

  • 1 <= primeFactors <= 10^9

Solution

Method 1 – Mathematical Optimization (Integer Break, Fast Power)

Intuition

To maximize the number of nice divisors, we want to split the primeFactors into as many 3’s as possible (integer break problem). This is because the product of numbers that sum to primeFactors is maximized when using as many 3’s as possible, with a few 2’s if needed. The answer is the product of these numbers, modulo 1e9+7.

Approach

  1. If primeFactors is 1, return 1.
  2. Otherwise, break primeFactors into as many 3’s as possible:
    • Let q = primeFactors // 3, r = primeFactors % 3.
    • If r == 0, answer is 3^q.
    • If r == 1, answer is 3^(q-1) * 4 (replace one 3+1 with 2+2).
    • If r == 2, answer is 3^q * 2.
  3. Use fast exponentiation to compute large powers modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int mod = 1e9+7;
    long long power(long long a, long long b) {
        long long ans = 1;
        while (b) {
            if (b & 1) ans = ans * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return ans;
    }
    int maxNiceDivisors(int pf) {
        if (pf == 1) return 1;
        int q = pf / 3, r = pf % 3;
        if (r == 0) return power(3, q);
        if (r == 1) return power(3, q-1) * 4 % mod;
        return power(3, q) * 2 % mod;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func maxNiceDivisors(pf int) int {
    mod := int(1e9+7)
    power := func(a, b int) int {
        ans := 1
        for b > 0 {
            if b&1 == 1 {
                ans = ans * a % mod
            }
            a = a * a % mod
            b >>= 1
        }
        return ans
    }
    if pf == 1 {
        return 1
    }
    q, r := pf/3, pf%3
    if r == 0 {
        return power(3, q)
    }
    if r == 1 {
        return power(3, q-1) * 4 % mod
    }
    return power(3, q) * 2 % mod
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    static final int MOD = 1000000007;
    private long power(long a, long b) {
        long ans = 1;
        while (b > 0) {
            if ((b & 1) == 1) ans = ans * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return ans;
    }
    public int maxNiceDivisors(int pf) {
        if (pf == 1) return 1;
        int q = pf / 3, r = pf % 3;
        if (r == 0) return (int)power(3, q);
        if (r == 1) return (int)(power(3, q-1) * 4 % MOD);
        return (int)(power(3, q) * 2 % MOD);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    private val mod = 1_000_000_007L
    private fun power(a: Long, b: Int): Long {
        var ans = 1L
        var base = a
        var exp = b
        while (exp > 0) {
            if (exp and 1 == 1) ans = ans * base % mod
            base = base * base % mod
            exp = exp shr 1
        }
        return ans
    }
    fun maxNiceDivisors(pf: Int): Int {
        if (pf == 1) return 1
        val q = pf / 3
        val r = pf % 3
        return when (r) {
            0 -> power(3, q).toInt()
            1 -> (power(3, q-1) * 4 % mod).toInt()
            else -> (power(3, q) * 2 % mod).toInt()
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def maxNiceDivisors(self, pf: int) -> int:
        mod = 10**9 + 7
        def power(a: int, b: int) -> int:
            ans = 1
            while b:
                if b & 1:
                    ans = ans * a % mod
                a = a * a % mod
                b >>= 1
            return ans
        if pf == 1:
            return 1
        q, r = divmod(pf, 3)
        if r == 0:
            return power(3, q)
        if r == 1:
            return power(3, q-1) * 4 % mod
        return power(3, q) * 2 % mod
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn max_nice_divisors(pf: i32) -> i32 {
        let mod_ = 1_000_000_007i64;
        fn power(mut a: i64, mut b: i32, mod_: i64) -> i64 {
            let mut ans = 1i64;
            while b > 0 {
                if b & 1 == 1 {
                    ans = ans * a % mod_;
                }
                a = a * a % mod_;
                b >>= 1;
            }
            ans
        }
        if pf == 1 {
            return 1;
        }
        let q = pf / 3;
        let r = pf % 3;
        if r == 0 {
            return power(3, q, mod_) as i32;
        }
        if r == 1 {
            return (power(3, q-1, mod_) * 4 % mod_) as i32;
        }
        (power(3, q, mod_) * 2 % mod_) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maxNiceDivisors(pf: number): number {
        const mod = 1e9 + 7;
        function power(a: number, b: number): number {
            let ans = 1;
            while (b > 0) {
                if (b & 1) ans = ans * a % mod;
                a = a * a % mod;
                b >>= 1;
            }
            return ans;
        }
        if (pf === 1) return 1;
        const q = Math.floor(pf / 3), r = pf % 3;
        if (r === 0) return power(3, q);
        if (r === 1) return power(3, q-1) * 4 % mod;
        return power(3, q) * 2 % mod;
    }
}

Complexity

  • ⏰ Time complexity: O(log n) — for fast exponentiation.
  • 🧺 Space complexity: O(1) — only a few variables are used.