文章目錄
-
- 1. 題目
- 2. 解題
1. 題目
給你一個正整數 primeFactors 。你需要構造一個正整數 n ，它滿足以下條件：
- n 質因數（質因數需要考慮重複的情況）的數目 不超過 primeFactors 個。
-
n 好因子的數目 最大化。
如果 n 的一個因子可以被 n 的每一個質因數整除，我們稱這個因子是 好因子 。
比方說，如果 n = 12 ，那麼它的質因數為 [2,2,3] ，那麼 6 和 12 是好因子，但 3 和 4 不是。
請你傳回 n 的好因子的數目。
由于答案可能會很大，請傳回答案對 10^9 + 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 <= 10^9 複制
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/maximize-number-of-nice-divisors
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
- 一個數有 primeFactors 個質因子
- 不同的質因子個數 n1,n2,…,nk, 這 k 個數的和為 primeFactors，且 k 個數的乘積最大（好因子數目最大）
- 參考 LeetCode 343. 整數拆分（DP），分成盡可能多的 3，不夠的用 2
- 外加快速幂，求 3 的大數次幂
class Solution {
int mod = 1e9+7;
public:
int maxNiceDivisors(int primeFactors) {
if(primeFactors <= 3)
return primeFactors;
if(primeFactors%3 == 0)
return mypow(3, primeFactors/3);
else if(primeFactors%3 == 1)
return mypow(3, primeFactors/3-1)*4LL%mod;
else
return mypow(3, primeFactors/3)*2LL%mod;
}
int mypow(int base, int n)
{
long long ans = 1, p = base;
while(n)
{
if(n&1)
ans = (ans*p)%mod;
p = (p*p)%mod;
n >>= 1;
}
return ans;
}
}; 複制
0 ms 5.8 MB C++
我的CSDN部落格位址 https://michael.blog.csdn.net/
長按或掃碼關注我的公衆号（Michael阿明），一起加油、一起學習進步！