原文发表于这里，公式被渲染的很难看。
Problem 88
一个自然数$N$如果能被至多两个自然数汇合$\{a_1,a_2,\cdots,a_k\}$同时用乘积和和示意，即$N=a_1+a_2+\cdots+a_k=a_1\times a_2\times\cdots\times a_k$，那么称为Product-sum number。
比方$6=1+2+3=1\times 2\times 3$。
给定一个固定大小$k$，能够找到一个最小的$N$是Product-sum number。对于$k=2,3,4,5,6$，最小$N$如下
$$\begin{aligned}
k=2:&&&4=2\times 2=2+2\
k=3:&&&6=1+2+3=1\times 2\times 3\
k=4:&&&8=1\times 1\times 2\times 4=1+1+2+4\
k=5:&&&8=1\times 1\times 2\times 2\times 2=1+1+2+2+2\
k=6:&&&12=1\times 1\times 1\times 1\times 2\times 6=1+1+1+1+2+6
\end{aligned}$$
因而$2\leq k\leq 6$，最小Product-sum number$N$之和是$4+6+8+12=30$，留神8只记录一次。
求$2\leq k\leq 12000$时，最小Product-sum number的$N$之和。
<!-- more -->
先预计下数据量，下限是12k，如果采纳暴力法，如果对于给定的$k$可能线性工夫得出对应的最小的$N$的话，复杂度也就144M，对于CPU而言，是很小的量级，如果可能$k\lg k$的工夫复杂度得出后果，也齐全是能够承受的。那么先依照暴力法思考下问题。
比方$k=12,000$，$2^k$是一个很大很大的值，显然12000个数的和不可能有那么大的，所以不须要真的遍历12000个数，其实$2^{15}=32768$就比12000大挺多的了，所以$k$的低15个数字就能决定乘积与和是否相等了，残余的数字都是1，很容易得出积与和。
既然只有15个数字就能决定的话，齐全不须要暴力求解了。
这里引入进位和加一的概念，把这15个数字当作15位，加一就是把最低为加一。进位呢？当乘积比和大的时候，就进一位，而后进位这个中央之后的数字放弃和前一位一样（这样做是为了不重不丢），这样乘积就会变小，比方$2\times 2\times 90$进位失去$2\times 3\times 3$，乘积从360降到18。
如何判断从哪里进位呢？上述形容是说进位后的每一位和进位的数字放弃一样，所以从低位向高位扫描，两两比拟，如果雷同，阐明是从上次进位留下的后果，后续没有通过加一的步骤，无须再进位，第一次须要不同的中央，高位加一示意进位的操作，高位之后的数字天然放弃和高位一样的数字。
上面是形容进位的函数
private static bool Carry(int[] digits){ for (int i = 0; i < digits.Length - 1; i++) { if (digits[i] != digits[i + 1]) { digits[i + 1]++; for (int j = 0; j <= i; j++) { digits[j] = digits[i + 1]; } return true; } } return false;}从最小值最低两位是2其余数字是1开始，加一，或者进位，直到进位也无奈无奈使得乘积再比和小（比方$2,3,3,3,3$进位失去$3,3,3,3,3$），或者无奈再进位（数字都一样），则完结整个过程。
这样失去一个汇合，每个元素是15个数字组成的汇合。那么对于每个$k$对应的最小值$N$都能用该汇合中某个元素示意，反过来想，这个汇合的每个元素，都决定了某个$k$值对应的$N$（这里不肯定是最小值）。通过过滤失去最小值是很容易。
当初问题是如果通过某个15个数字的汇合反推失去对应的$k$。我计算失去这15个数字的乘积p与和s，如果$p\geq s$且$p-s\leq 12000-15$（不要超出下限），令$d=p-s$，差了一些，然而不多，那么$k$比15大的话，求和时候后面有若干个一减少$s$，使得$p=s$，后面若干个是多少个？$d$个！所有这里的$p$就是一个宽度为$d+15$的Product-sum number。$p<s$的话，相当于后面的1多了，原理是一样的。
上面的代码反馈的就是上述的剖析。
// 定义`ks`，用于保留各个宽度k对应的`Product-sum number`// 咱们从k=2开始，所以第零个和第一个初始化成0，前面初始化成最大值。int[] ks = new int[Max + 1];ks[0] = 0;ks[1] = 0;for (int i = 2; i < ks.Length; i++){ ks[i] = int.MaxValue;}// 0开始是低位int[] digits = new int[15] { 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };do{ // 计算差值，填充 diff+15 对应的 `Product-sum number` // 这里有一个大小的判断以存取最小值 int product = digits.Aggregate(1, (a, b) => a * b); int sum = digits.Sum(); int diff = product - sum; if (diff <= Max - 15 && diff >= -13 && ks[diff + 15] > product) { ks[diff + 15] = product; } // 每次迭代要么须要进位，要么进行加一操作 // 如果无奈进位，迭代完结 if (diff >= Max - 15) { bool ok = Carry(digits); if (!ok) { break; } } else { digits[0]++; }} while (true);有了一系列宽度$k$对应的最小Product-sum number，去重求和失去最初的后果。