Count sum of multiples of a number below N with O(1) complexity?

Question

We are given two numbers M and N. We need to count the sum of all the integers below N, which are divisible by M.

Is it possible to solve with O(1) complexity?

I know it is a very simple program and can be easily done with a loop. But I was wondering if it is possible to apply some kind of formula or something to directly count the sum of numbers which are divisible by M below N.

Answer 1

Indeed there is an O(1) solution:

First exploit integer arithmetic to compute n = N / M. n is then the number of terms in an arithmetic progression with first term and common difference equal to M.

The sum (which comes from the formula for an arithmetic progression) is then

n * (1 + n) * M / 2

For example, consider N = 23, and M = 5. You're after 5 + 10 + 15 + 20 which is 50. The closed form solution evaluates to 4 * 5 * 5 / 2 which is also 50.

Answer 2

L:=floor(M/N)

M + 2*M + 3*M + ... + L*M 

= M (1+2+3+4+...+L)

this can be solved with the wikipedia summation

= M*(L*(L+1)/2)

This can be calculated in O(1)