1808. Maximize Number of Nice Divisors - cocoder39/coco39_LC GitHub Wiki

1808. Maximize Number of Nice Divisors

Given p1, p2, ... pk are distinct prime numbers, where N = p1^a1 + p2^a2 + ... + pk^ak so a1 + a2 + .. + ak = primeFactors, then the maximize number of nice divisors is a1 * a2 * ... ak

In other words, given a1 + a2 + .. + ak = primeFactors, find the max product a1 * a2 * ... ak. This is exactly 343. Integer Break

T = O(log primeFactors)

class Solution:
    def maxNiceDivisors(self, primeFactors: int) -> int:
        MOD = 10**9 + 7
        if primeFactors <= 3:
            return primeFactors
        if primeFactors % 3 == 0:
            return pow(3, primeFactors // 3, MOD)
        if primeFactors % 3 == 1:
            return pow(3, (primeFactors -4) // 3, MOD) * 4 % MOD
        return pow(3, primeFactors // 3, MOD) * 2 % MOD