Conta somma di multipli di un numero inferiore a N con O (1) complessità?

Question

c'è dato due numeri M e N. Dobbiamo contare la somma di tutti i numeri interi sotto N, che sono divisibili per M.

E 'possibile risolvere con O (1) la complessità?

So che è un programma molto semplice e può essere fatto facilmente con un ciclo. Ma mi chiedevo se è possibile applicare un qualche tipo di formula o qualcosa per contare direttamente la somma dei numeri che sono divisibili per M sotto N.

Answer 1

Infatti v'è un O (1) soluzione:

First exploit numero intero aritmetico per calcolare n = N/M. n è quindi il numero di termini in una progressione aritmetica con il primo termine e la differenza comune uguale a M.

La somma (che viene dalla formula per una progressione aritmetica) è quindi

n * (1 + n) * M/2

Ad esempio, si consideri N = 23, M = 5. Sei dopo 5 + 10 + 15 + 20 che è 50. la soluzione in forma chiusa viene valutato come 4 * 5 * a 5/2 che è anche 50.

Answer 2

L:=floor(M/N) 

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

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

questo può essere risolto con l'wikipedia summation

0.123.

Questo può essere calcolato in O (1)