https://leetcode-cn.com/problems/maximize-number-of-nice-divisors/
PS：这题编号有点大，不知道是不是临时分配的，后面会改成小编号
这题最后简化出来就是要求解 `max(x * y * z * ..) st. x + y + z + … <=n`.
首先可以肯定的是，我们肯定会取和为N，这个可以通过反证法来证明。
然后可以证明，假设分割成为k份的话，使用平均分肯定比不平均分效果要好。
所以最后问题就是选取切分成为多少份。我没有办法证明，但是直觉认为这个是个凸函数，有个全局最优解，所以可以做个二分。
- 选取 F(K-1), F(K), F(K+1)
- 如果 F(K)比两个都要大的话，那么选择K
- 如果 F(K-1) <= F(K+1) 的话，那么可以把区间下游置位K+1
- 否则把上游置位K-1.
这个乘积会比较大，所以可以考虑使用 `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