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 mostprimeFactors
. - The number of nice divisors of
n
is maximized. Note that a divisor ofn
is nice if it is divisible by every prime factor ofn
. For example, ifn = 12
, then its prime factors are[2,2,3]
, then6
and12
are nice divisors, while3
and4
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; };