Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1808.html

1808. Maximize Number of Nice Divisors

Level

Hard

Description

You are given a positive integer primeFactors. You are asked to construct a positive integer n that satisfies the following conditions:

  • The number of prime factors of n (not necessarily distinct) is at most primeFactors.
  • The number of nice divisors of n is maximized. Note that a divisor of n is nice if it is divisible by every prime factor of n. For example, if n = 12, then its prime factors are [2,2,3], then 6 and 12 are nice divisors, while 3 and 4 are not.

Return the number of nice divisors of n. Since that number can be too large, return it modulo 10^9 + 7.

Note that a prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. The prime factors of a number n is a list of prime numbers such that their product equals n.

Example 1:

Input: primeFactors = 5

Output: 6

Explanation: 200 is a valid value of n.

It has 5 prime factors: [2,2,2,5,5], and it has 6 nice divisors: [10,20,40,50,100,200].

There is not other value of n that has at most 5 prime factors and more nice divisors.

Example 2:

Input: primeFactors = 8

Output: 18

Constraints:

  • 1 <= primeFactors <= 10^9

Solution

If primeFactors <= 3, simply return primeFactors.

For greater values, consider the prime factors of n. The smallest nice divisor of n is the product of all distinct prime factors of n. For example, the prime factors of 12 are 2,2,3, so the smmalest nice divisor of 12 is 2*3=6. If n = p1^a1 * p2^a2 * ... * pk*ak, where a1 + a2 + ... + ak <= primeFactors, then n has a1 * a2 * ... * ak nice divisors. The problem is to find the maximum value of a1 * a2 * ... * ak.

To get the maximum value, there should be as many numbers 3 as possible, and the remaining numbers should be 2 (at most two numbers 2). Calculate the product using pow function and deal with large values accordingly.

  • class Solution {
    static final int MODULO = 1000000007;

    public int maxNiceDivisors(int primeFactors) {
        if (primeFactors <= 3)
            return primeFactors;
        int quotient = primeFactors / 3;
        int remainder = primeFactors % 3;
        if (remainder == 0)
            return (int) (pow(3, quotient) % MODULO);
        else if (remainder == 1)
            return (int) (pow(3, quotient - 1) * 4 % MODULO);
        else
            return (int) (pow(3, quotient) * 2 % MODULO);
    }

    public long pow(long x, int n) {
        long power = 1;
        while (n > 0) {
            if (n % 2 == 1)
                power = power * x % MODULO;
            x = x * x % MODULO;
            n /= 2;
        }
        return power;
    }
}

############

class Solution {
    public int maxNiceDivisors(int primeFactors) {
        if (primeFactors < 4) {
            return primeFactors;
        }
        final int mod = (int) 1e9 + 7;
        if (primeFactors % 3 == 0) {
            return (int) qmi(3, primeFactors / 3, mod);
        }
        if (primeFactors % 3 == 1) {
            return (int) (4 * qmi(3, primeFactors / 3 - 1, mod) % mod);
        }
        return (int) (2 * qmi(3, primeFactors / 3, mod) % mod);
    }

    private long qmi(long a, long k, long p) {
        long res = 1;
        while (k != 0) {
            if ((k & 1) == 1) {
                res = res * a % p;
            }
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }
}

  • // OJ: https://leetcode.com/problems/maximize-number-of-nice-divisors/
// Time: O(logN)
// Space: O(1)
class Solution {
    long mod = 1e9+7;
public:
    long modpow(long base, long exp) {
        long ans = 1;
        while (exp > 0) {
            if (exp & 1) ans = (ans * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        return ans;
    }
    int maxNiceDivisors(int N) {
        if (N <= 3) return N;
        long ans;
        switch (N % 3) {
            case 0: ans = modpow(3, N / 3); break;
            case 1: ans = 2 * 2 * modpow(3, N / 3 - 1); break;
            case 2: ans = 2 * modpow(3, N / 3); break;
        }
        return ans % mod;
    }
};

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



  • func maxNiceDivisors(primeFactors int) int {
	if primeFactors < 4 {
		return primeFactors
	}
	const mod int = 1e9 + 7
	if primeFactors%3 == 0 {
		return qmi(3, primeFactors/3, mod)
	}
	if primeFactors%3 == 1 {
		return 4 * qmi(3, primeFactors/3-1, mod) % mod
	}
	return 2 * qmi(3, primeFactors/3, mod) % mod
}

func qmi(a, k, p int) int {
	res := 1
	for k != 0 {
		if k&1 == 1 {
			res = res * a % p
		}
		k >>= 1
		a = a * a % p
	}
	return res
}

  • /**
 * @param {number} primeFactors
 * @return {number}
 */
var maxNiceDivisors = function (primeFactors) {
    if (primeFactors < 4) {
        return primeFactors;
    }
    const mod = 1e9 + 7;
    const qpow = (a, n) => {
        let ans = 1;
        for (; n; n >>= 1) {
            if (n & 1) {
                ans = Number((BigInt(ans) * BigInt(a)) % BigInt(mod));
            }
            a = Number((BigInt(a) * BigInt(a)) % BigInt(mod));
        }
        return ans;
    };
    const k = Math.floor(primeFactors / 3);
    if (primeFactors % 3 === 0) {
        return qpow(3, k);
    }
    if (primeFactors % 3 === 1) {
        return (4 * qpow(3, k - 1)) % mod;
    }
    return (2 * qpow(3, k)) % mod;
};

All Problems

All Solutions