题目描述

https://leetcode-cn.com/problems/maximize-number-of-nice-divisors/

算法1

(快速幂 + 找规律) $O(logn)$

分析

可看我的注释，不过写的有些乱
这题和 剪绳子 这题十分相似，不过需要用到快速幂求解. 难点在于分析出需要如何拆分数才能使答案，也就是好因子的数目最大。
首先构造一个数 $n = p_1^{a1} * p_2^{a2} * … p_k^{ak}$
然后要保证$ a_1 + a_2 + … a_k = m$ 且 乘积最大
因为由好因子要能被$p_1,p_2,…p_k$所整除，所以由乘法定理，好因子的个数就为质因数分配个数的乘积
重点来了，如何拆分？
1. 那么可以考虑, 若某个质因数它的指数ai >= 5, 那么把他拆分为3, ai-3,也就是说它的指数为3，存在另一个质因数的指数为$ai - 3$, 那么此时所得到的解必然会是优的，因为$3 * (ai - 3) - ai > 0$
2. 再有， 当$ai == 4$ 时， 它必然可以拆为 2 * 2, 此时对最优解无影响

通过上述两个分析，可得出最优解肯定都是由2，3组成，因为1对于答案没有影响，所以可以忽略
接下来分析，答案中必然最多存在2个2,前面分析了ai >= 4, 那么当ai <= 3, 因为2 * 2 * 2 < 3 * 3, 也就是说如果存在3个指数为2，那么把其中两个换为3会更好

至此，得到结论
1. 拆分结果中只存在2， 3
2. 拆分结果不存在大于等于3个2
3. 当$m \% 3 == 0$时， 只有 $m / 3$个3, 当 $m \% 3 == 1$时，只有 $(m - 4) / 3$ 个3，2个2， 当$m \% 3 == 2$时，只有$(m - 2) / 3$个3，1个2

C++ 代码

/*
a1 + a2 + ... + ak = m
n = p1^a1 * p2 ^ a2 * ... pl ^ ak
求f(n) = a1 * a2 ... ak的最大值
给定一个正整数m，把m拆分为若干个正整数的和，使得拆分出的正整数乘积最大
假定一个最优解 a1 + a2 + ... + ai == m
若ai >= 5 , 把他拆分为 3, ai - 3, 则有3 * (ai - 3) - ai > 0 , 所以拆分后可得到更优的解
考虑 ai == 4, 则ai 只可对半拆， 即两个2
考虑 1 <= ai <= 3 , 则可以拆为3个2和2个3，由于3的乘积更大，所以拆为2个3
最多只能有2个2
*/
typedef long long LL;
const int mod = 1e9 + 7;

class Solution {
public:

    LL qmi(LL a, LL b)
    {
        LL res = 1;
        while(b)
        {
            if(b & 1) res = res * a % mod;
            b >>= 1;
            a = a * a % mod; 
        }
        return res;
    }

    int maxNiceDivisors(int m) {
        if(m <= 3) return m;
        else if(m % 3 == 0) return qmi(3, m / 3) % mod;
        else if(m % 3 == 1) return qmi(3, (m - 4) / 3) * 4 % mod;
        return qmi(3, (m - 2) / 3) * 2 % mod;
    }
};