本文涉及知识点
质因数 数学
LeetCode1808. 好因子的最大数目
给你一个正整数 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
唯一分解定理
令 n = a1b1a2b2… \dots…
a1,b1… \dots…都是质因数，b1,b2… \dots…是对应质因数的数量。
则：y = a1x1a2x2… \dots…
x1 ∈ \in∈[1,b1] x2 ∈ \in∈[1,b2] 都是好因子。
故好因子的数量为：b1*b2… \dots…
显然bi不会大于3，否则拆分成2和bi-2 更优或相等。
显然也不会有3个2,否则拆分3× \times× 3 更优。
除非n 为1,否则b1不会为1。否则任意一个bj相加。
1 == n % \%% 3 ， 2个2，其它全部3。
2 == n% \%% 3 ，1个2，其它全部3。
代码
template<int MOD = 1000000007> class C1097Int { public: C1097Int(long long llData = 0) :m_iData(llData% MOD) { } C1097Int operator+(const C1097Int& o)const { return C1097Int(((long long)m_iData + o.m_iData) % MOD); } C1097Int& operator+=(const C1097Int& o) { m_iData = ((long long)m_iData + o.m_iData) % MOD; return *this; } C1097Int& operator-=(const C1097Int& o) { m_iData = (m_iData + MOD - o.m_iData) % MOD; return *this; } C1097Int operator-(const C1097Int& o) { return C1097Int((m_iData + MOD - o.m_iData) % MOD); } C1097Int operator*(const C1097Int& o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int& operator*=(const C1097Int& o) { m_iData = ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator==(const C1097Int& o)const { return m_iData == o.m_iData; } bool operator<(const C1097Int& o)const { return m_iData < o.m_iData; } C1097Int pow(long long n)const { C1097Int iRet = 1, iCur = *this; while (n) { if (n & 1) { iRet *= iCur; } iCur *= iCur; n >>= 1; } return iRet; } C1097Int PowNegative1()const { return pow(MOD - 2); } int ToInt()const { return m_iData; } private: int m_iData = 0;; }; class Solution { public: int maxNiceDivisors(int primeFactors) { if (1 == primeFactors) { return 1; }; C1097Int<> biRet = 1; if (1 == primeFactors % 3) { biRet *= 4; primeFactors -= 4; } if (2 == primeFactors % 3) { biRet *= 2; primeFactors -= 2; } biRet *= C1097Int<>(3).pow(primeFactors / 3); return biRet.ToInt(); } };
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
