Найдите сумму всех чисел между 1 и N, делящимися на x или y

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

Ответы

Ответ 1

Да. Вы можете аннулировать цикл for и найти сумму в постоянное время.

В соответствии с Принцип включения-исключения суммируя кратные x и кратные y и вычитая общий множественный ( s), которые были добавлены дважды, должны предоставить нам требуемую сумму.

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), может быть вычислен в постоянное время.

Таким образом, требуемая сумма также может быть вычислена в постоянное время.

EDIT:

Вышеупомянутое обсуждение справедливо только тогда, когда x и y являются сопутствующими параметрами. Если нет, нам нужно использовать LCM(x,y) вместо x*y. Существует много способов найти LCM, один из которых состоит в том, чтобы разделить продукт на GCD. Теперь GCD невозможно вычислить в постоянное время, но его временная сложность может быть значительно меньше линейного.

Ответ 2

Если число делится на 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;