1808. 最大化优雅除数的数目

Hard

题目描述

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

n 的质因数个数（不一定不同）最多为 primeFactors。
n 的优雅除数的数目最大化。注意，如果 n 的一个除数能被 n 的每个质因数整除，那么这个除数是优雅的。例如，如果 n = 12，它的质因数为 [2,2,3]，那么 6 和 12 是优雅除数，而 3 和 4 不是。

返回 n 的优雅除数的数目。由于答案可能很大，返回对 10^9 + 7 取余的结果。

注意质数是大于 1 且不能表示为两个更小自然数乘积的自然数。一个数 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^9

解题思路

这道题的关键在于理解优雅除数的定义和如何最大化它们的数目。

核心观察：

对于数 n = p1^a1 * p2^a2 * ... * pk^ak，优雅除数的数目等于 (a1+1) * (a2+1) * ... * (ak+1)
题目要求质因数总数最多为 primeFactors，即 a1 + a2 + ... + ak ≤ primeFactors
问题转化为：给定和为 primeFactors 的正整数序列，如何使它们的乘积最大

数学分析： 通过数学推导可以得出：

当因子大于4时，可以拆分成更小的因子获得更大乘积
最优解只包含2和3
当有三个或更多2时，可以用两个3替换获得更大乘积（因为 33 > 22*2）
因此最优策略是尽可能多地使用3，剩余部分用2填充

具体策略：

特殊情况：当 primeFactors ≤ 4 时直接返回
一般情况：计算能使用多少个3，剩余部分的处理方式：
- 余数为0：全部用3
- 余数为1：减少一个3，用两个2替代（因为 22 > 31）
- 余数为2：添加一个2

由于指数可能很大，需要使用快速幂算法计算 3^x mod (10^9+7)。

代码实现

class Solution {
public:
    int maxNiceDivisors(int primeFactors) {
        const int MOD = 1e9 + 7;
        
        if (primeFactors <= 4) return primeFactors;
        
        long long result = 1;
        int quotient = primeFactors / 3;
        int remainder = primeFactors % 3;
        
        if (remainder == 0) {
            result = power(3, quotient, MOD);
        } else if (remainder == 1) {
            result = (power(3, quotient - 1, MOD) * 4) % MOD;
        } else {
            result = (power(3, quotient, MOD) * 2) % MOD;
        }
        
        return result;
    }
    
private:
    long long power(long long base, int exp, int mod) {
        long long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
};

class Solution:
    def maxNiceDivisors(self, primeFactors: int) -> int:
        MOD = 10**9 + 7
        
        if primeFactors <= 4:
            return primeFactors
        
        quotient, remainder = divmod(primeFactors, 3)
        
        if remainder == 0:
            return pow(3, quotient, MOD)
        elif remainder == 1:
            return (pow(3, quotient - 1, MOD) * 4) % MOD
        else:
            return (pow(3, quotient, MOD) * 2) % MOD

public class Solution {
    public int MaxNiceDivisors(int primeFactors) {
        const int MOD = 1000000007;
        
        if (primeFactors <= 4) return primeFactors;
        
        int quotient = primeFactors / 3;
        int remainder = primeFactors % 3;
        
        if (remainder == 0) {
            return (int)Power(3, quotient, MOD);
        } else if (remainder == 1) {
            return (int)(Power(3, quotient - 1, MOD) * 4 % MOD);
        } else {
            return (int)(Power(3, quotient, MOD) * 2 % MOD);
        }
    }
    
    private long Power(long baseNum, int exp, int mod) {
        long result = 1;
        baseNum %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * baseNum) % mod;
            }
            baseNum = (baseNum * baseNum) % mod;
            exp >>= 1;
        }
        return result;
    }
}

var maxNiceDivisors = function(primeFactors) {
    const MOD = 1000000007;
    
    if (primeFactors <= 4) {
        return primeFactors;
    }
    
    function powMod(base, exp, mod) {
        let result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
    
    if (primeFactors % 3 === 0) {
        return powMod(3, primeFactors / 3, MOD);
    } else if (primeFactors % 3 === 1) {
        return (4 * powMod(3, Math.floor(primeFactors / 3) - 1, MOD)) % MOD;
    } else {
        return (2 * powMod(3, Math.floor(primeFactors / 3), MOD)) % MOD;
    }
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大O表示法
时间复杂度	O(log primeFactors)
空间复杂度	O(1)

时间复杂度主要来自快速幂算法，空间复杂度为常数级别。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目