1808

1808. Maximize Number of Nice Divisors (Hard)

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 109 + 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.

 

Example 1:

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:

Input: primeFactors = 8
Output: 18

 

Constraints:

• 1 <= primeFactors <= 109

Related Topics:
Math

Similar Questions:

• Integer Break (Medium)

Solution 1.

Consider the example case where F = 5, 200 is a valid value of n, [2,2,2,5,5] are the prime factors.

To construct nice divisors, we can get them by multiplying 1~3 number 2s and 1~2 number 5s. So there are 3 * 2 = 6 nice divisors.

So this question is equivalent to: Given a number F, find an optimal way of breaking F = a + b + c + d + ..., such that a * b * c * d ... is maximized. (In this problem, a, b, c, d... are the counts of different primes)

We can reuse the solution to Breaking an Integer to get Maximum Product or 343. Integer Break (Medium)

// OJ: https://leetcode.com/problems/maximize-number-of-nice-divisors/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
    long mod = 1e9+7;
public:
    long modpow(long base, long exp) {
        long ans = 1;
        while (exp > 0) {
            if (exp & 1) ans = (ans * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        return ans;
    }
    int maxNiceDivisors(int N) {
        if (N <= 3) return N;
        long ans;
        switch (N % 3) {
            case 0: ans = modpow(3, N / 3); break;
            case 1: ans = 2 * 2 * modpow(3, N / 3 - 1); break;
            case 2: ans = 2 * modpow(3, N / 3); break;
        }
        return ans % mod;
    }
};