Formatted question description: https://leetcode.ca/all/1808.html

# 1808. Maximize Number of Nice Divisors

## Level

Hard

## Description

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`

.

**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 <= 10^9`

## Solution

If `primeFactors <= 3`

, simply return `primeFactors`

.

For greater values, consider the prime factors of `n`

. The smallest nice divisor of `n`

is the product of all distinct prime factors of `n`

. For example, the prime factors of 12 are 2,2,3, so the smmalest nice divisor of 12 is 2*3=6. If `n = p1^a1 * p2^a2 * ... * pk*ak`

, where `a1 + a2 + ... + ak <= primeFactors`

, then `n`

has `a1 * a2 * ... * ak`

nice divisors. The problem is to find the maximum value of `a1 * a2 * ... * ak`

.

To get the maximum value, there should be as many numbers 3 as possible, and the remaining numbers should be 2 (at most two numbers 2). Calculate the product using `pow`

function and deal with large values accordingly.

```
class Solution {
static final int MODULO = 1000000007;
public int maxNiceDivisors(int primeFactors) {
if (primeFactors <= 3)
return primeFactors;
int quotient = primeFactors / 3;
int remainder = primeFactors % 3;
if (remainder == 0)
return (int) (pow(3, quotient) % MODULO);
else if (remainder == 1)
return (int) (pow(3, quotient - 1) * 4 % MODULO);
else
return (int) (pow(3, quotient) * 2 % MODULO);
}
public long pow(long x, int n) {
long power = 1;
while (n > 0) {
if (n % 2 == 1)
power = power * x % MODULO;
x = x * x % MODULO;
n /= 2;
}
return power;
}
}
```