找到1和N之间的所有数字的总和,可以用x或y整除

Question

假设我们有3数字N,x而且y总是数字>=1.

N值将大于x和y和x会大于y.

现在我们需要找到1到N之间的所有数字之和,它们可以被x或y整除.

我想出了这个:

sum = 0;
for(i=1;i<=N;i++)
{
  if(i%x || i%y)
    sum += i;
}

有没有更好的方法来找到避免for循环的总和？

我现在已经好好打了很多天,但没有更好的东西.

如果值N具有上限,我们可以使用查找方法来加速该过程.

感谢大家.

我想要一个基于C/C++的解决方案.是否有内置函数来执行此操作？或者我必须编写算法代码？

Answer 1

是.你可以完全取消for循环,并在恒定时间内找到总和.

根据包含 - 排除原理,总结多次x和多次y并减去两次加入的公共倍数应该给出我们所需的总和.

Required Sum = sum of ( multiples of x that are <= N ) +      
               sum of ( multiples of y that are <= N ) -
               sum of ( multiples of (x*y) that are <= N )

例:

N = 15
x = 3
y = 4

Required sum = ( 3 + 6 + 9 + 12 + 15) +  // multiples of 3
               ( 4 + 8 + 12 ) -          // multiples of 4
               ( 12 )                    // multiples of 12

如上所示,我们不得不减去12两次,因为它是一个常见的倍数.

整个算法O(1)怎么样？

让sum(x, N)是倍数的总和x,其小于或等于N.

sum(x,N) = x + 2x + ... + floor(N/x) * x
         = x * ( 1 + 2 + ... + floor(N/x) )
         = x * ( 1 + 2 + ... + k)    // Where k = floor(N/x)
         = x * k * (k+1) / 2         // Sum of first k natural num = k*(k+1)/2

现在k = floor(N/x)可以在恒定时间内计算.

一旦k知道sum(x,N)就可以在恒定时间内计算.

因此,所需的总和也可以在恒定时间内计算.

编辑:

上述讨论仅适用于x并且y是共同素数的情况.如果不是,我们需要LCM(x,y)代替x*y.有许多方法可以找到LCM,其中一种方法是通过GCD划分产品.现在GCD不能在恒定时间内计算,但其时间复杂度可以显着小于线性时间.