【唯一分解定理 数学】1808好因子的最大数目

简介: 【唯一分解定理 数学】1808好因子的最大数目

本文涉及知识点

质因数 数学

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++**实现。

相关文章
|
数据采集 存储 前端开发
关于数仓建设及数据治理的超全概括 (一)
本文分为两大节介绍,第一节是数仓建设,第二节是数据治理,内容较长,还请耐心阅读!
968 0
关于数仓建设及数据治理的超全概括 (一)
|
弹性计算 Cloud Native Devops
云效DevStudio体验
阿里云中提供了在线编辑工具DevStudio,让开发更加便捷。
2330 0
云效DevStudio体验
|
9月前
|
人工智能 算法 计算机视觉
【01】opencv项目实践第一步opencv是什么-opencv项目实践-opencv完整入门以及项目实践介绍-opencv以土壤和水滴分离的项目实践-人工智能AI项目优雅草卓伊凡
【01】opencv项目实践第一步opencv是什么-opencv项目实践-opencv完整入门以及项目实践介绍-opencv以土壤和水滴分离的项目实践-人工智能AI项目优雅草卓伊凡
282 63
【01】opencv项目实践第一步opencv是什么-opencv项目实践-opencv完整入门以及项目实践介绍-opencv以土壤和水滴分离的项目实践-人工智能AI项目优雅草卓伊凡
|
数据采集 存储 安全
Python爬虫实战:利用代理IP爬取某瓣电影排行榜并写入Excel(附上完整源码)
Python爬虫实战:利用代理IP爬取某瓣电影排行榜并写入Excel(附上完整源码)
329 0
Python爬虫实战:利用代理IP爬取某瓣电影排行榜并写入Excel(附上完整源码)
|
12月前
|
Java 程序员
Java 面试高频考点:static 和 final 深度剖析
本文介绍了 Java 中的 `static` 和 `final` 关键字。`static` 修饰的属性和方法属于类而非对象,所有实例共享;`final` 用于变量、方法和类,确保其不可修改或继承。两者结合可用于定义常量。文章通过具体示例详细解析了它们的用法和应用场景。
195 3
|
11月前
|
前端开发 JavaScript API
现代前端框架中的响应式编程实践
现代前端框架中的响应式编程实践
195 0
|
NoSQL Linux MongoDB
MongoDB提供的这些工具
【6月更文挑战第8天】MongoDB提供的这些工具
307 6
win10取消ie浏览器自动跳转edge浏览器
win10取消ie浏览器自动跳转edge浏览器
358 4
|
存储 缓存 负载均衡
图解一致性哈希算法,看这一篇就够了!
近段时间一直在总结分布式系统架构常见的算法。前面我们介绍过布隆过滤器算法。接下来介绍一个非常重要、也非常实用的算法:一致性哈希算法。通过介绍一致性哈希算法的原理并给出了一种实现和实际运用的案例,带大家真正理解一致性哈希算法。
24750 64
图解一致性哈希算法,看这一篇就够了!
|
数据安全/隐私保护
基于SpringBoot+Vue+Mysql+Java 高校校园点餐系统(附源码)下
基于SpringBoot+Vue+Mysql+Java 高校校园点餐系统(附源码)