https://leetcode.com/problems/maximize-number-of-nice-divisors

In fact, this problem is very similar to problem 343. Integer Break https://leetcode.com/problems/integer-break/, let me explain why:

Imagine, that we have number m = p1^a1*p2^a2*...*pk^ak, this is standard representation of number, where p1, ..., pk are some prime numbers and a1, ..., ak some integer powers. Then total number of nice divisors can be calculated by a1*...*ak: just using combinatorics rules: first one can be choosen by a1 options, second by a2 and so on. Also, we are given, that a1 + ... + ak <= n, where by n here I defined primeFactors for simplicity. So, the problem now looks like:

Given a1 + ... + ak <= n find maximum a1 * ... ak.

Let us prove, that it is always better when we make numbers equal to 2 or 3. Indeed, if we have bigger, we can split it to two parts: like 4 -> 2*2, 5 -> 2*3, 6 -> 3*3 and so on. Moreover, if we have 2, 2, 2, it is always better to replace it to 3, 3. So in the end: optimal configuration has only 2 and 3 and number of 2 is not more than two. Let us just check all 3 cases: n gives reminders 0, 1, 2 when divided by 3 and evaluate answer.

Complexity: time complexity is O(log n), because function pow with given modulo M will use expontiation trick with doubling of exponent. Space complexity is O(1).

class Solution:
    def maxNiceDivisors(self, n):
        M = 10**9 + 7
        if n <= 3: return n
        if n % 3 == 0: return pow(3, n//3, M)
        if n % 3 == 1: return (pow(3, (n-4)//3, M) * 4) % M
        return (2*pow(3, n//3, M)) % M

If you like the solution, you can upvote it on leetcode discussion section: Problem 1808