LC_1808

from functools import lru_cache

class Solution:
    def maxNiceDivisors(self, primeFactors):
        res = 1
        for num_pieces in range(1, primeFactors // 2 + 1):
            if primeFactors % num_pieces == 0:
                each_piece_cnt = primeFactors // num_pieces
                # 均值定理
                res = max(res, each_piece_cnt ** num_pieces)
            else:
                each_piece_cnt = self._helper(num_pieces, primeFactors)
                rest = primeFactors - each_piece_cnt * (num_pieces - 1)
                temp = each_piece_cnt ** (num_pieces - 1)
                temp *= rest
                res = max(res, temp)

        return res % (10 ** 9 + 7)

    
    @lru_cache(None)
    def _helper(self, num_pieces, total):
        each_piece_cnt = total // num_pieces
        while each_piece_cnt * num_pieces < total:
            each_piece_cnt += 1
        return each_piece_cnt