短租网站那家做的好处,H5酒店静态网站建设开题报告范文,网页设计作业10个页面,步骤图文章目录1. 题目2. 解题1. 题目
给你一个正整数 primeFactors 。你需要构造一个正整数 n #xff0c;它满足以下条件#xff1a;
n 质因数#xff08;质因数需要考虑重复的情况#xff09;的数目 不超过 primeFactors 个。n 好因子的数目 最大化。 如果 n 的一个因子可以…
文章目录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 1e97;
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(n1)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阿明一起加油、一起学习进步
