问数论算法

EN

所以AB数可以写成10^(n+1) A + B。，这意味着对所有A, B的求和，总数等于

|R| 10^(n+1) Sum(A in L) + |L| Sum(B in R)

在你的例子中，

|L| = 6
|R| = 6
Sum(A in L) = 24
Sum(B in R) = 17
n = 3

当插入上述公式时，得到14 502。

这使得运行时集合的大小从二次减少到线性，因此您应该会看到相当大的改进。

接下来的部分，我没有充分充实，因为我没有时间，但他们觉得他们应该工作：

• 首先，注意使用以下方法计算Sum(A in L)是很简单的 1+2+ .+n= n(n-1)/2 如果没有L不包含重复的约束的话。不过，您可以通过利用a非常小的事实来解决这一问题:使用三角数公式迭代计算和1, .., a，并使用这些信息避免多次计算乘积。
• 对于Sum(B in R)，请注意，当您比较y和x^y时，最多只能更改第一个lg(a)位。因此，您可以将x^y的和分为两个和:一个处理来自lg(a)+1向上的比特，它只依赖于b；另一个，更复杂的和，处理从lg(a)向下产生的位，它依赖于a和b。

编辑:OP要求我扩展如何快速计算Sum(A in L)。在以前的编辑中，这一节中有一段内容，但实际上我已经坐下来，现在已经完成了它，而不是随意地在我的脑海中反复地处理它。结果也比我预期的要复杂得多，所以我很抱歉没能早点坐下来处理它。

所以我们要做的是取所有不同的产品x*y的和，比如1 <= x <= a和1 <= y <= b。那么，这是非常困难的，所以让我们从一个更简单的问题开始:给定两个整数x1, x2和x1 < x2，我们如何计算所有不同乘积x1*y或x2*y的和，其中1 <= y <= b

如果我们放弃了明确性标准，这就很容易了:它很简单

x1*Sum(b) + x2*Sum(b)

其中Sum(j)表示通过j包含的整数之和，并且可以用高斯公式计算三角数。因此，我们可以再一次将问题简化为更简单的问题:我们如何才能找到所有以左、右两种形式出现的产品的总和？

那么，两个产品是相等的，如果

x1*y1 == x2*y2

这正是在x1*y1 == x2*y2 == k*LCM(x1, x2)时发生的，其中LCM是最低公共倍数，k是一些整数。

在所有k上的和，所以1 <= k*LCM(x1, x2) <= x1*b是

R(x1, x2) = LCM(x1, x2) * Sum(x1*b/LCM(x1, x2))

其中R代表“重复”。这意味着我们所有不同产品的和，x1*y或x2*y，其中1 <= y <= b是

x1*Sum(b) + x2*Sum(b) - R(x1, x2)

接下来，让我们将R的定义扩展到三个变量x1 < x2 < x3上，如

R(x1, x2, x3) = LCM(x1, x2, x3) * Sum(x1*b/LCM(x1, x2, x3))

同样，对于4个变量、5个变量等，则三个x1 < x2 < x3的不同乘积之和为

x1*Sum(b) + x2*Sum(b) + x3*Sum(b) - R(x1, x2) - R(x1, x3) - R(x2, x3) + R(x1, x2, x3)

由包容排除原则。

所以，让我们利用这个。定义

Sum for x = 1: 1*Sum(b)
Sum for x = 2: 2*Sum(b) - R(2, 1)
Sum for x = 3: 3*Sum(b) - R(3, 2) - R(3, 1) + R(3, 2, 1)

等。那么，到x = a为止，所有这些和的和就是所有不同乘积的和。

编辑：@tenos把它变成了一个有用的解决方案。他注意到，由于i*Sum(b)包含许多重复，我们可以用I*sum(k.b)，k= max(b/minPrimeFactor(i) + 1，i)代替。

此外，当使用包含排除原理时，许多不必要的计算可以被剪除。例如，如果R(1,2) = NULL，则不需要计算R(1,2,3)，R(1，2，4).等。事实上，当b很大时，有许多R(i，..j) = NULL。