文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個(gè)正整數(shù) primeFactors 。你需要構(gòu)造一個(gè)正整數(shù) n ，它滿足以下條件：

• n 質(zhì)因數(shù)（質(zhì)因數(shù)需要考慮重復(fù)的情況）的數(shù)目 不超過 primeFactors 個(gè)。
• n 好因子的數(shù)目 最大化。
  如果 n 的一個(gè)因子可以被 n 的每一個(gè)質(zhì)因數(shù)整除，我們稱這個(gè)因子是 好因子 。
  比方說，如果 n = 12 ，那么它的質(zhì)因數(shù)為 [2,2,3] ，那么 6 和 12 是好因子，但 3 和 4 不是。

請(qǐng)你返回 n 的好因子的數(shù)目。
由于答案可能會(huì)很大，請(qǐng)返回答案對(duì) 10^9 + 7 取余 的結(jié)果。

請(qǐng)注意，一個(gè)質(zhì)數(shù)的定義是大于 1 ，且不能被分解為兩個(gè)小于該數(shù)的自然數(shù)相乘。一個(gè)數(shù) n 的質(zhì)因子是將 n 分解為若干個(gè)質(zhì)因子，且它們的乘積為 n 。

示例 1： 輸入：primeFactors = 5 輸出：6 解釋：200 是一個(gè)可行的 n 。 它有 5 個(gè)質(zhì)因子：[2,2,2,5,5] ，且有 6 個(gè)好因子：[10,20,40,50,100,200] 。 不存在別的 n 有至多 5 個(gè)質(zhì)因子，且同時(shí)有更多的好因子。示例 2： 輸入：primeFactors = 8 輸出：18提示： 1 <= primeFactors <= 10^9

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximize-number-of-nice-divisors
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 一個(gè)數(shù)有 primeFactors 個(gè)質(zhì)因子
• 不同的質(zhì)因子個(gè)數(shù) n1,n2,…,nk, 這 k 個(gè)數(shù)的和為 primeFactors，且 k 個(gè)數(shù)的乘積最大（好因子數(shù)目最大）
• 參考 LeetCode 343. 整數(shù)拆分（DP），分成盡可能多的 3，不夠的用 2
• 外加快速冪，求 3 的大數(shù)次冪

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;elsereturn 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/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1808. 好因子的最大数目（整数拆分，乘积最大）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。