Найти сумму всех чисел от 1 до N, кратную x или y - PullRequest
Новая
       11

Найти сумму всех чисел от 1 до N, кратную x или y

11 голосов
/ 17 декабря 2010

Скажем, у нас есть 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 ++. Есть ли встроенная функция для этого? Или я должен закодировать алгоритм?

Ответы [ 2 ]

27 голосов
/ 17 декабря 2010

Да.Вы можете полностью аннулировать цикл 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 не может быть вычислен в постоянном времени, но его сложность времени может быть значительно меньше, чем линейное время.

4 голосов
/ 17 декабря 2010

Если число делится на X, оно должно быть кратно x. Если число делится на Y, оно должно быть кратным y.

Полагаю, если вы выполните цикл for для всех кратных x и y и избежите дублирования, вы должны получить тот же ответ.

Из моей головы что-то типа: 

sum = 0
for( i=x; i<=n; i+=x)
    sum += i;

for( i=y; i<=n; i+=y)
    if( y % x != 0 )
        sum += i;
...