更好的阅读体验

题目大意：

题目链接

输入输出：

思路分析：

假设质因子的数目为k时:n可以表示为：Pi表示质因子，Ai表示对应质因子的个数

根据题目要求满足:
$${\color{Red} {\scriptsize {\textstyle \sum_{1}^{k}ai}=primeFactors} } $$
而好因子的要求必须被每一个质因子整除，所以每一个质因子都要选一次，类似与求约数个数那道题，好因子的数目个数为：
$$ {\color{Red} {\scriptsize \prod_{i}^{k}ai} } $$
问题转化为：343. 整数拆分
这道经典数学问题的贪心解法为：将n的质因子拆分为只包含2和3：
证明如下：假设最优的质因子排列中存在一个Ai满足：$$ {\color{Red} {\tiny ai\ge 5} }$$
不妨将ai拆成3和(ai-3),他们的乘积满足：
$$ {\color{Red} {\tiny 3*(ai-3)\ge ai}} \equiv {\tiny 2*ai\ge 9 } $$

将ai拆出一个3后结果不会变差，这样质因子ai满足a1<=4:
同理ai=4时可以拆成2*2，结果不变，追后的质因子只会包含2和3，
对于同样的和比如6，有 3*3>2*2*2,优先拆出3；

注意这道题的数据范围比较大，用快速幂加速

AC代码：

const int mod=1e9+7;
class Solution {
public:
    int qmi(int a,int b,int p){
        int res=1;
        while(b){
            if(b&1) res=1ll*res*a%p;
            a=1ll*a*a%p;
            b>>=1;
        }
        return res;
    }
    int maxNiceDivisors(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        int p=n/3,r=n%3;
        if(r==0){
            return qmi(3,p,mod);
        }
        else if(r==1){
            return qmi(3,p-1,mod)*4ll%mod;
        }
        else if(r==2){
            return qmi(3,p,mod)*2ll%mod;
        }
        return 0;
    }
};