class Solution {
public:
int maxNiceDivisors(int primeFactors) {
}
};
1808. 好因子的最大数目
给你一个正整数 primeFactors 。你需要构造一个正整数 n ，它满足以下条件：
n 质因数（质因数需要考虑重复的情况）的数目 不超过 primeFactors 个。n 好因子的数目最大化。如果 n 的一个因子可以被 n 的每一个质因数整除，我们称这个因子是 好因子 。比方说，如果 n = 12 ，那么它的质因数为 [2,2,3] ，那么 6 和 12 是好因子，但 3 和 4 不是。请你返回 n 的好因子的数目。由于答案可能会很大，请返回答案对 109 + 7 取余 的结果。
请注意，一个质数的定义是大于 1 ，且不能被分解为两个小于该数的自然数相乘。一个数 n 的质因子是将 n 分解为若干个质因子，且它们的乘积为 n 。
示例 1：
输入：primeFactors = 5 输出：6 解释：200 是一个可行的 n 。 它有 5 个质因子：[2,2,2,5,5] ，且有 6 个好因子：[10,20,40,50,100,200] 。 不存在别的 n 有至多 5 个质因子，且同时有更多的好因子。
示例 2：
输入：primeFactors = 8 输出：18
提示：
1 <= primeFactors <= 109原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-07-05 10:03:42
func maxNiceDivisors(primeFactors int) int {
if primeFactors < 5 {
return primeFactors
}
three := primeFactors / 3 // 拆分3的个数
primeFactors = primeFactors % 3 // 余数
if primeFactors == 1 {
primeFactors += 3
three -= 1
}
mod := int(mypow(three) % 1000000007)
return (mod * max(1, primeFactors)) % 1000000007
}
func mypow(n int) int64 {//快速幂
var res int64 = 1
var x int64 = 3
for n > 0 {
if (n & 1) == 1 {
res *= x
res %= 1000000007
}
x *= x
x %= 1000000007
n >>= 1
}
return res
}
func max(a, b int) int { if a < b { return b }; return a }
python3 解法, 执行用时: 48 ms, 内存消耗: 16 MB, 提交时间: 2023-07-05 09:59:10
class Solution:
def maxNiceDivisors(self, primeFactors: int) -> int:
if primeFactors < 5: return primeFactors
three = primeFactors // 3 # 拆分3的个数
primeFactors = primeFactors % 3 # 余数
if primeFactors == 1:
primeFactors += 3
three = three - 1
mod = pow(3, three, 10**9+7)
return (mod * max(1,primeFactors)) % (10**9+7)
python3 解法, 执行用时: 40 ms, 内存消耗: 15.9 MB, 提交时间: 2023-07-05 09:56:33
import math
class Solution:
def maxNiceDivisors(self, primeFactors: int) -> int:
def quick_algorithm(a: int, b: int, c: int):
a = a % c
ans = 1
while b != 0:
if b & 1:
ans = (ans * a) % c
b >>= 1
a = (a * a) % c
return ans
if primeFactors == 1:
return 1
rest = primeFactors % 3
if rest == 0:
return quick_algorithm(3, primeFactors // 3, 10 ** 9 + 7) % (10 ** 9 + 7)
if rest == 1:
return quick_algorithm(3, primeFactors // 3 - 1, 10 ** 9 + 7) * 4 % (10 ** 9 + 7)
if rest == 2:
return quick_algorithm(3, primeFactors // 3, 10 ** 9 + 7) * 2 % (10 ** 9 + 7)