好因子的最大数目

标签: 递归 数学

难度: Hard

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

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

请你返回 n 的好因子的数目。由于答案可能会很大，请返回答案对 109 + 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 <= 109

Submission

运行时间: 28 ms

内存: 16.1 MB

class Solution:
    def maxNiceDivisors(self, primeFactors: int) -> int:
        MOD = 10**9 + 7
        
        # 快速幂算法
        def fast_pow(base, exponent):
            result = 1
            while exponent:
                if exponent & 1:
                    result = result * base % MOD
                base = base * base % MOD
                exponent >>= 1
            return result
        
        # 处理特殊情况
        if primeFactors <= 3:
            return primeFactors
        
        # 根据primeFactors对3取余的结果进行分类讨论
        quotient = primeFactors // 3
        remainder = primeFactors % 3
        
        if remainder == 0:
            return fast_pow(3, quotient)
        elif remainder == 1:
            return fast_pow(3, quotient - 1) * 4 % MOD
        else:
            return fast_pow(3, quotient) * 2 % MOD

Explain

题解基于分解质因数的方式来最大化好因子数目。通过分析可以发现，将整数n分解为多个3的乘积时，可以得到更多的好因子。具体策略为：1. 当primeFactors小于或等于3时，直接返回primeFactors，因为无法形成更多的好因子。2. 当primeFactors大于3时，首先计算将primeFactors尽可能多地分为3的组合，计算剩余的质因数数目。如果剩余1个，最优策略是使用一个2和两个3组成的数（即2*3*3），如果剩余2个，使用两个2更优（即2*2*3）。使用快速幂算法来高效计算大数的乘积的模。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def maxNiceDivisors(self, primeFactors: int) -> int:
        MOD = 10**9 + 7
        
        # 快速幂算法，用于高效计算大数的幂
        def fast_pow(base, exponent):
            result = 1
            while exponent:
                if exponent & 1:
                    result = result * base % MOD
                base = base * base % MOD
                exponent >>= 1
            return result
        
        # 处理特殊情况，当质因数较少时，直接返回
        if primeFactors <= 3:
            return primeFactors
        
        # 将质因数尽量分为3的组合，并处理剩余部分
        quotient = primeFactors // 3
        remainder = primeFactors % 3
        
        if remainder == 0:
            return fast_pow(3, quotient)
        elif remainder == 1:
            # 优先组合成一个较大数，如4*3^(n-1)
            return fast_pow(3, quotient - 1) * 4 % MOD
        else:
            # 处理剩余为2的情况，组合成2*3^n
            return fast_pow(3, quotient) * 2 % MOD

Explore

选择3的乘积来最大化好因子的数目基于一个数学原理：若要使得一组数的乘积固定时，这些数的和越大，则它们的乘积构成的因子数目通常越多。在给定总和的情况下，尽量使得各分组之间的大小差异最小（即尽量均匀分配），可以获得较大的乘积。例如，3+3+3+3比2+2+2+4来得大。数学上可以通过不等式证明，当所有数均为3时，其乘积最大。这是因为当分解的数均为3时，3的指数总和在不超过原有质因数的前提下达到最大，从而使得乘积的分解项（好因子）最大化。这一原理可以通过拉格朗日乘数法或者算术几何均值不等式来进行数学证明。

当剩余的质因数为1时，如果直接使用3个3（即3*3*3=27）与使用一个2和两个3（即2*3*3=18）相比，虽然27大于18，但关键在于如何使用已有的质因数总数。如果总质因数为10，那么使用3*3*3*1的组合，相当于浪费了一个1，而2*3*3可以更有效地利用这个额外的1（变为2），形成2*(3*3)=18，而不是27*1=27。因此，在总质因数固定的情况下，选择2*3*3可以避免浪费质因数，使得所有质因数都能得到有效利用。

快速幂算法在计算时优先考虑处理指数中的奇数情况，其目的是为了确保算法的效率。当指数为奇数时，可以将当前底数乘到结果中，并将指数减少1转化为偶数，这样就可以通过指数的每次除以2（右移一位操作）来减半处理次数。这种方法利用了位运算的高效性，能够显著减少乘法操作的次数。每当指数为奇数时，通过处理这种情况，可以确保算法的每一步都是必要的，从而加快乘幂计算的速度。