索伦对邓布利多和梅林说... - MariaDB.org

这听起来像一个蹩脚的跨界玩笑，但它不是。这是一个蹩脚的跨界数学问题。我必须承认，当我读到它时，它没有这些名字，但我想让它变得更史诗一些。所以，

索伦对邓布利多和梅林说，我终于抓住了你们两个。现在我将选取两个大于一、小于一百的数字。邓布利多将知道它们的乘积，梅林将知道它们的总和。如果你们这些傻瓜能告诉我我选了什么数字，我就放你们自由。否则，我将杀死你们俩。
于是他照做了，在邓布利多耳边低语，然后又在梅林耳边低语。
邓布利多看着梅林，叹了口气承认：“我无法说出这些数字。” 梅林耸了耸肩，“我早就知道了。” “哦”——邓布利多眨了眨眼——“但这样我就能说出它们了。” “我也是，”梅林迅速补充道。
当然，他们说出来了。故事结束。

人们常说，如果你只有一把锤子，那么一切都看起来像钉子。而我目前只有一个 SQL 数据库。让我们用它来解开这个故事。

很可能可以用一个巨大的 SQL 查询¹ 来解决这个问题，但一步一步来要容易得多，为此我们需要一个表

CREATE TABLE t AS SELECT s1.seq a, s2.seq b
    FROM seq_2_to_99 s1, seq_2_to_99 s2
        WHERE s1.seq < s2.seq;

表就在这里。一个漂亮的表，其中包含索伦可能选择的所有数字组合。如果你更喜欢遵循 SQL 标准或只是使用另一个数据库，你需要使用 WITH 子句来填充表，但我在这里不受现实世界的限制。

数字有很多组合，总和与乘积也有很多不同的值。有些很常见，有些很罕见。某些乘积只出现一次

SELECT a,b,a+b,a*b FROM t GROUP BY a*b HAVING COUNT(*)=1;
+----+----+-----+------+
| a  | b  | a+b | a*b  |
+----+----+-----+------+
|  2 |  3 |   5 |    6 |
|  2 |  4 |   6 |    8 |
...
| 97 | 99 | 196 | 9603 |
| 98 | 99 | 197 | 9702 |
+----+----+-----+------+

但这些不是我们要找的数字。如果邓布利多听到“8”，他会立刻知道这两个数字。或者如果他听到“9603”。或者，比如说，“187”（两个质数的乘积）。他听到的数字肯定不在这个列表上。

但是等等，梅林知道。无论梅林听到的数字是什么，都有很多方法可以将它分成两个加数。将它们相乘会得到许多不同的乘积。梅林知道邓布利多无法弄清楚这些数字，因为从梅林的总和的加数中可能得到的乘积都不在上面的列表上。否则梅林不会如此确定。换句话说，梅林听到的数字不在上表的第三列中。

是时候修剪表格了。让我们移除所有我们知道索伦不可能选择的数字，也就是梅林不可能听到其总和的数字

DELETE FROM t WHERE a+b IN
    (SELECT a+b FROM t GROUP BY a*b HAVING COUNT(*)=1);

回到邓布利多。他一听到梅林睿智的话语，就知道自己得救了。他当然是一位巫师，他在脑海中进行了所有上述推导，比你读这篇博文的速度快得多。该表仍然有 145 行，我们不知道索伦的数字是什么。但邓布利多知道它们的乘积——这帮助他找到了对他生命和自由至关重要的那一行。

为邓布利多高兴的是，我们知道无论他知道的乘积是什么，它在表中一定只出现了一次。现在让我们移除所有其他行

DELETE FROM t WHERE a*b IN
    (SELECT a*b FROM t GROUP BY a*b HAVING COUNT(*)>1);

至于梅林——邓布利多的话就是他所需的一切。他不知道数字的乘积，只知道它们的总和。但他现在知道这个乘积在现在只有 86 行的表中只出现了一次。知道这一点和总和就足以让他脱困了。显然，他的总和在那里也只出现了一次。真是走运！

这最后一点信息也是我们所需要的

SELECT a,b,a+b,a*b FROM t GROUP BY a+b HAVING COUNT(*)=1;
+---+----+-----+-----+
| a | b  | a+b | a*b |
+---+----+-----+-----+
| 4 | 13 |  17 |  52 |
+---+----+-----+-----+

1) 事实证明，从上面组装出一个符合 SQL 标准的一站式查询解决方案相当容易。无需进一步解释，就在这里

WITH RECURSIVE seq (i) AS
(
  SELECT 2 UNION ALL SELECT i+1 FROM seq WHERE i < 99
),
step1 (a,b) AS (
  SELECT s1.i, s2.i FROM seq s1, seq s2 WHERE s1.i < s2.i
),
step2 AS (
  SELECT * FROM step1 WHERE a+b NOT IN (SELECT SUM(a+b) FROM step1 GROUP BY a*b HAVING COUNT(*)=1)
),
step3 AS (
  SELECT * FROM step2 WHERE a*b NOT IN (SELECT a*b FROM step2 GROUP BY a*b HAVING COUNT(*)>1)
)
SELECT SUM(a),SUM(b),a+b,SUM(a*b) FROM step3 GROUP BY a+b HAVING COUNT(*)=1;

这在 PostgreSQL、SQLite、SQL Server（移除关键字 RECURSIVE 后）、Oracle（在 SELECT 2 中额外添加 FROM DUAL 后）、DB2（与 Oracle 相同，但使用不同的 1 行表）以及 MySQL（不使用 ONLY_FULL_GROUP_BY，我在默认设置下无法使其工作）中有效。