问

关于数论的算法

博客百度2 发布于 2023-02-10 14:16

给出两个正整数a,b(1 <= a <= 30,1 <= b <= 10000000),并定义两个不可重复的集合L和R,

L = {x * y | 1 <= x <= a, 1 <= y <= b, x,y is integer}

R = {x ^ y | 1 <= x <= a, 1 <= y <= b, x,y is integer},

^是异或操作

对于任何两个整数:A∈L,B∈R,我们将B格式化为n + 1(n是b的十进制数字)十进制数字(在B前面填0),然后将B连接到A的末尾并获得一个新的整数AB.

计算所有生成的整数AB的总和(如果总和超过,只返回"sum mod 1000000007",mod表示模块化运算)

注意:算法的时间不超过3秒

我的算法非常简单:我们可以很容易地得到集合R中的最大数,并且R中的元素是0,1,2,3 ... maxXor,(元素max(a,b)可能不在R中) ,使用哈希表计算集L. 但是当a = 30,b = 100000时算法消耗4秒.

举个例子:

a = 2, b = 4, so

L = {1 * 1, 1 * 2, 1 * 3, 1 * 4, 2 * 1, 2 * 2, 2 * 3, 2 * 4} =  {1, 2, 3, 4, 6, 8}

R =  {1^1,1^2,1^3,1^4,2^1,2^2,2^3,2^4} =  {0, 1, 2, 3, 5, 6}

所有生成的整数AB是:

{

100, 101, 102, 103, 105, 106,

200, 201, 202, 203, 205, 206,

300, 301, 302, 303, 305, 306,

400, 401, 402, 403, 405, 406,

600, 601, 602, 603, 605, 606,

800, 801, 802, 803, 805, 806

}

所有AB的总和是14502

1 个回答

所以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^ys 的总和分成两个总和:一个处理来自lg(a)+1向上的位并且仅取决于b,以及第二个更复杂的求和处理来自lg(a)向下的位并且取决于a和b.

编辑:OP要求我扩展如何快速计算Sum(A in L).在以前的编辑中,本节中有一些东西,但实际上我已经坐下来完成了它,而不是随意地将它击打在我脑海中.事实证明它比我想象的要复杂得多,所以我很抱歉没有坐下来及早完成它@tenos.

所以我们想要做的是利用所有不同的产品的总和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)
```
where Sum(j)表示1通过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.
2023-02-10 14:18 回答

小佛瞌睡蓝

撰写答案

今天，你开发时遇到什么问题呢？

立即提问

热门标签