零、写在前面
这是打卡的第十天，由于今天的第二题有一定的难度，需要我花费比较大的篇幅做题解，这是第二篇，主要讲解第三题。我增加了一道题作为这道题的第一步辅助理解。上一篇在
[解题报告]《算法零基础100讲》(第10讲) 因子分解和枚举(上)https://blog.csdn.net/qq_17593855/article/details/121052656
https://blog.csdn.net/qq_17593855/article/details/121052656
一、预备知识
⚠这部分不是特别难，只要你能理解，你就可以很容易的写这道题
整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
最简单的方式肯定是穷举所有可能算最大成绩，但是这种东西一看就是会有结论的，我们何不推一推呢？
根据高中数学知识我们知道柯西不等式，几何平均大于等于调和平均：
这道题已知的是
要求的是 
的最大值不妨记为
易知 
也就是
对右边求导我们得到
所以我们可以知道当n/x = e 的时候函数取最大值。但是原题只让我们分解为正整数，我们知道e大约是2.7左右，所以我们把n分解为尽量多的3时函数可以取到最大值。但是当最后只剩1的时候需要和前面一个三合并拆成两个2这样最大。（因为柯西告诉我们这些数相差越小乘积越大 其实4也需要验证 但是4 =2 x 2所以没差啦）
if(n == 1) return 1; if(n % 3 == 0) return pow(3,n/3); else if(n % 3 == 1) return pow(3,n /3 -1)*4; else return pow(3,n/3)*2;
结果是不是很简洁？这个其实记得住把？记不住过程请记住结论。可以试试我给的习题一练习一下。
二分快速幂
这道题还需要知道这个知识点，不然的话会超时。。。
首先有一个引论 
其实就是积对一个数取余等于两个数分别取余然后乘积再对c取余
证明其实很简单 假如a = X1x c+Y1,b = X2 x c +Y2
就可以得到ab = (X1 x X2Y1 +X1Y2 + X2)x c + Y1 x Y2 这里结论是不是很显然？
然后我们做一点点推广可以得到这样的递推式
利用上面的结论得到：
我们把它做成一个函数形式就是
long long f(long long a, long long b, long long c) { if (b == 0) return 1 % c; long long v = f(a*a % c, (b>>1), c); if (b & 1) v = v * a % c; return v; }
注：>>1与/2是没有任何区别的，完全和上面的递推式相同，目的就是为了二分减小b的值快速得到答案。
二、课后习题详解
整数拆分
343. 整数拆分
https://leetcode-cn.com/problems/integer-break/
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
思路
上面讲的结论用一用就好了嘛，不然真去拆分？但是这里说明了至少两个所以需要对1、2、3单独去判断。
int integerBreak(int n){ if(n == 1 || n == 2) return 1; if(n == 3) return 2; if(n % 3 == 0) return pow(3,n/3); else if(n % 3 == 1) return pow(3,n /3 -1)*4; else return pow(3,n/3)*2; }
结果分析
无敌，也是一种淡淡的忧伤~
好因子的最大数目
1808. 好因子的最大数目
https://leetcode-cn.com/problems/maximize-number-of-nice-divisors/
给你一个正整数 primeFactors 。你需要构造一个正整数 n ，它满足以下条件：
- n 质因数（质因数需要考虑重复的情况）的数目 不超过 primeFactors 个。
- n 好因子的数目最大化。如果 n 的一个因子可以被 n 的每一个质因数整除，我们称这个因子是 好因子 。比方说，如果 n = 12 ，那么它的质因数为 [2,2,3] ，那么 6 和 12 是好因子，但 3 和 4 不是。
请你返回 n 的好因子的数目。由于答案可能会很大，请返回答案对 109 + 7 取余 的结果。
请注意，一个质数的定义是大于 1 ，且不能被分解为两个小于该数的自然数相乘。一个数 n 的质因子是将 n 分解为若干个质因子，且它们的乘积为 n 。
思路
一共n个质因数，好因子其实就是质因子的乘积得到的，比如例子给的2,2,3有三个质因数，其中两个不相同，最终的好因子数就是2x1。易知如果一个数的质因数为则所有的好因子数目就是k·q·w个。这么来看的话和前面的整数是不是就是一样的了？
直接利用相关的结论就好了，但是这题的数据量太大了，如果直接计算会超时并且会上溢出。所以要用二分快速幂。
long long f(long long a, long long b, long long c) {//二分快速幂 讲过了。。告辞 if (b == 0) return 1 % c; long long v = f(a*a % c, (b>>1), c); if (b & 1) v = v * a % c; return v; } int maxNiceDivisors(int primeFactors){//这里就是把上面的整数拆分的计算换一种方式 其它一样。 if(primeFactors == 1) return 1; long long ans = 1; if(primeFactors % 3 == 0){ ans = f(3,primeFactors / 3,1000000007); } else if(primeFactors % 3 == 1) { ans = f(3,primeFactors / 3 - 1 ,1000000007); ans = (ans*4)%(1000000007); } else{ ans = f(3,primeFactors / 3,1000000007);; ans = (ans*2)%(1000000007); } return ans; }
结果分析
在非人的领域，同样无敌~
课后总结
之前有人说说有问题都是数学，我不信。
今天我信了。。。
加油 一起学习！
