1808-好因子的最大数目

给你一个正整数 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

已知:

• a1, a2, a3, …… an 是质数
• a1^b1 * a2^b2 * …… * an^bn = sum;
• b1 + b2 + …… + bn = n; 其中n已知

求：

• 好因子个数，比如有 3 个 2， 2 个 5，那么好因子个数就相当于在 3个2 里取出3种情况(1个2， 2个2， 3个2)，在 2个5 里取出2种情况(1个5，2个5)，相乘即可，即好因子个数 = 3 * 2 = 6
• 上面这种算法其实就是 好因子个数 = b1 * b2 * …… * bn 的最大值

那么求好因子个数的最大值就是求：

• 已知 b1 + b2 + …… + bn = n
• 求 b1 * b2 * …… * bn 的最大值

然后就发现这是一道原题 –> 343. 整数拆分
需要注意的是幂次太大会溢出需要取模，因此在快速幂里取模 –> 50. Pow(x, n)

代码：

const int modN = 1e9 + 7;
class Solution {
public:
    int maxNiceDivisors(int primeFactors) {
        int n = primeFactors;
        if (n <= 3) {
            return n;
        }
        long long ans = 0;
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            ans = myPow(3, quotient);
        } else if (remainder == 1) {
            ans = myPow(3, quotient - 1) * 4;
        } else {
            ans = myPow(3, quotient) * 2;
        }
        return ans % modN;
    }
    long long myPow(long long x, int n) {
        long long ans = 1;
        n = abs(n);
        while(n){
            if(n % 2 != 0){
                ans *= x;
                ans %= modN;
            }
            x *= x;
            x %= modN;
            n /= 2;
        }
        return ans;
    }
};