清MM两个数题解释 - 珍珠湾ART

这两个数到底是什么?

孙膑，庞涓都是鬼谷子的徒弟，他们都是绝顶聪明的人。
一天鬼出了这道题目：他从2到99中选出两个不同的整数，把和告诉庞，把积告诉孙。
庞说：我虽然不能确定这两个数是什么，但是我肯定你也不知道这两个数是什么。
孙说：我本来的确不知道，但是听你这么一说，我现在能够确定这两个数字了。
庞说：既然你这么说，我现在也知道这两个数字是什么了。
这两个数到底是什么？

这一类题经常在取值范围上有所不同。有时有解（4，13），有时无解。假设是从2到N，且庞的数为P，孙的数为S。（应该反过来。）由庞的第一句话可知：1）S不是两个素数的积，2）S的最大素因子不超过N的一半。为保证这两点，P要满足下列条件：1）P是奇数，2）P-2不是素数，3）P不超过大于N/2的最小素数。满足前两个条件的数有11，17，23，27，29，35，37，41，47，...。根据第三个条件这个数列在接近N/2的某处截断。

这些数的每一个都可以用不同方式分解成两个数的和，并形成乘积。由孙的话，S只能用一种形式表成上述乘积，52是这样的数，其他的还有很多，像24，28，等。由庞的第二句话，P的分解中只有一个是这种数，其余都有两种或以上。从最后这个条件可以得出最小取值范围：

17 = 2+15 = 3+14 = 4+13 = 5+12 = 6+11 = 7+10 = 8+9，对应乘积30，42，52，60，66，70，72。我们需要其他六个数都有两种分解。30 = 2*15 = 5*6， 42 = 3*14 = 21*2，60 = 5*12 =3*20，66 = 11*6 = 33*2，70 = 7*10 = 35*2，72 = 8*9 = 3*24。其中最大的是35+2= 37。这要求庞涓的数列包括37，即N至少是62。

综上所述，N<62时无解，N>=62时（4，13）为解。可以证明这时解是唯一的，不过很繁琐。