LC 5716. 好因子的最大数目

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

PS：这题编号有点大，不知道是不是临时分配的，后面会改成小编号

这题最后简化出来就是要求解 `max(x * y * z * ..) st. x + y + z + … <=n`.

首先可以肯定的是，我们肯定会取和为N，这个可以通过反证法来证明。

然后可以证明，假设分割成为k份的话，使用平均分肯定比不平均分效果要好。

所以最后问题就是选取切分成为多少份。我没有办法证明，但是直觉认为这个是个凸函数，有个全局最优解，所以可以做个二分。

这个乘积会比较大，所以可以考虑使用 `log2(x)` 来做代理。

最后在做幂计算的时候，需要使用快速计算方法，而不能使用迭代。不然如果这个k比较大的话，也会出现超时的问题。 

class Solution:
    def maxNiceDivisors(self, primeFactors: int) -> int:
        import math
        n = primeFactors

        def split(k):
            if k == 0 or k > n: return 0
            avg = n // k
            r = n - k * avg
            # there are (r) (avg+1) , and (k-r) avg
            # ravg + r + kavg - ravg = r + kavg = n
            value = r * math.log2(avg + 1) + (k - r) * math.log2(avg)
            # print(k, avg, r, value, 2 ** value)
            return value

        def test():
            s, e = 1, n
            while s < e:
                m = (s + e) // 2
                # print(s, e, m)
                a = split(m - 1)
                b = split(m)
                c = split(m + 1)
                if b > a and b > c:
                    return m
                if a <= c:
                    s = m + 1
                else:
                    e = m - 1
            return s

        MOD = 10 ** 9 + 7

        # b ^ t
        def mul(b, t):
            ans = 1
            while t:
                if t & 0x1:
                    ans = ans * b
                    ans = ans % MOD
                t = t >> 1
                b = b * b
                b = b % MOD
            return ans

        k = test()
        avg = n // k
        r = n - avg * k
        ans = 1 * mul(avg + 1, r)
        ans = ans % MOD
        ans = ans * mul(avg, k - r)
        ans = ans % MOD
        return ans