What is the key insight in Maximize Number of Nice Divisors?

The key insight is that if n = p1^a1 * p2^a2 * ... * pk^ak, then the number of nice divisors is a1 * a2 * ... * ak, because each distinct prime must appear at least once in the divisor. That turns the problem into maximizing a product with a fixed sum of primeFactors.

Why do we break primeFactors into mostly 3s?

For integer partitions with maximum product, 3 is the most efficient chunk. Using as many 3s as possible gives the best result, except when you would leave a remainder of 1, in which case you replace 3 + 1 with 2 + 2.

Why is the answer for primeFactors = 5 equal to 6?

The best split is 3 + 2, whose product is 6. One construction is 2^3 * 5^2 = 200, and its nice divisors count is 3 * 2 = 6 because the exponent choices must include both distinct primes.

Do I need recursion for the Math plus Recursion pattern here?

Not for the partition logic. The recursion usually appears in fast modular exponentiation, where you compute powers by squaring and halving the exponent, but an iterative binary exponentiation version is equally good.

What are the exact edge cases for LeetCode 1808?

When primeFactors is 1, 2, or 3, the answer is primeFactors directly. For larger values, use the remainder cases: remainder 0 gives 3^k, remainder 1 gives 3^(k-1) * 4, and remainder 2 gives 3^k * 2, all modulo 1000000007.

#1808

Hard

auto_awesome数学·递归

LeetCode 题解工作台

好因子的最大数目

给你一个正整数 primeFactors 。你需要构造一个正整数 n ，它满足以下条件： n 质因数（质因数需要考虑重复的情况）的数目不超过 primeFactors 个。 n 好因子的数目最大化。如果 n 的一个因子可以被 n 的每一个质因数整除，我们称这个因子是好因子。比方说，如果 n =…

数学递归数论

题目描述

给你一个正整数 primeFactors 。你需要构造一个正整数 n ，它满足以下条件：

n 质因数（质因数需要考虑重复的情况）的数目 不超过 primeFactors 个。
n 好因子的数目最大化。如果 n 的一个因子可以被 n 的每一个质因数整除，我们称这个因子是 好因子 。比方说，如果 n = 12 ，那么它的质因数为 [2,2,3] ，那么 6 和 12 是好因子，但 3 和 4 不是。

请你返回 n 的好因子的数目。由于答案可能会很大，请返回答案对 10⁹ + 7 取余的结果。

请注意，一个质数的定义是大于 1 ，且不能被分解为两个小于该数的自然数相乘。一个数 n 的质因子是将 n 分解为若干个质因子，且它们的乘积为 n 。

示例 1：

输入：primeFactors = 5
输出：6
解释：200 是一个可行的 n 。
它有 5 个质因子：[2,2,2,5,5] ，且有 6 个好因子：[10,20,40,50,100,200] 。
不存在别的 n 有至多 5 个质因子，且同时有更多的好因子。

示例 2：

输入：primeFactors = 8
输出：18

提示：

1 <= primeFactors <= 10⁹

lightbulb

解题思路

方法一：问题转换 + 快速幂

我们可以将 $n$ 进行质因数分解，即 $n = a_1^{k_1} \times a_2^{k_2} \times\cdots \times a_m^{k_m}$ ，其中 $a_i$ 为质因子，而 $k_i$ 为质因子 $a_i$ 的指数。由于 $n$ 的质因子个数不超过 $primeFactors$ 个，因此 $k_1 + k_2 + \cdots + k_m \leq primeFactors$ 。

而根据题意描述，我们知道 $n$ 的好因子要满足能被所有的质因子整除，也即是说 $n$ 的好因子需要包含 $a_1 \times a_2 \times \cdots \times a_m$ 作为因数。那么好因子的个数 $k= k_1 \times k_2 \times \cdots \times k_m$ ，即 $k$ 为 $k_1, k_2, \cdots, k_m$ 的乘积。要最大化好因子的个数，也即是说我们要将 primeFactors 拆分成 $k_1, k_2, \cdots, k_m$ ，使得 $k_1 \times k_2 \times \cdots \times k_m$ 最大。因此问题转换为：将整数 primeFactors 拆分成若干个整数的乘积，使得乘积最大。

接下来，我们只需要分情况讨论。

如果 $primeFactors \lt 4$ ，那么直接返回 primeFactors 即可。
如果 $primeFactors$ 为 $3$ 的倍数，那么我们将 primeFactors 拆分成 $3$ 的倍数个 $3$ ，即 $3^{\frac{primeFactors}{3}}$ 。
如果 $primeFactors$ 除以 $3$ 余 $1$ ，那么我们将 primeFactors 拆分成 $\frac{primeFactors}{3} - 1$ 个 $3$ ，再乘以 $4$ ，即 $3^{\frac{primeFactors}{3} - 1} \times 4$ 。
如果 $primeFactors$ 除以 $3$ 余 $2$ ，那么我们将 primeFactors 拆分成 $\frac{primeFactors}{3}$ 个 $3$ ，再乘以 $2$ ，即 $3^{\frac{primeFactors}{3}} \times 2$ 。

以上过程中，我们利用快速幂取模求解。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They want you to notice that nice divisors count as a product of exponent sizes, not to enumerate divisors of n.
question_mark
They expect the integer-break insight that mostly 3s maximize the product under a fixed sum.
question_mark
They are checking whether you can combine number theory reasoning with safe modulo power for very large primeFactors.

warning

常见陷阱

外企场景

error
Returning 1 for primeFactors = 2 or 3 because of generic integer break logic, even though this problem allows using all factors directly and the answer should be 2 or 3.
error
Leaving a remainder 1 as 3 + 1, which loses value compared with converting it to 2 + 2.
error
Building n or trying candidate factorizations explicitly, which misses the reduction and cannot scale to 10^9.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Ask for the actual exponent partition instead of only the maximum count, which still ends in mostly 3s with a small tail adjustment.
arrow_right_alt
Replace nice divisors with ordinary divisors, changing the count formula from a1 * a2 * ... * ak to (a1 + 1)(a2 + 1)... and altering the optimization target.
arrow_right_alt
Force exactly k distinct primes in n, which adds another constraint to the exponent partition and changes the best split.

help

常见问题

外企场景

继续练习

#1799 N 次操作后的最大分数和 #1819 序列中不同最大公约数的数目 #1823 找出游戏的获胜者