Finden Sie die Summe aller Zahlen zwischen 1 und N teilbar durch entweder x oder y

Question

sagen, wir haben 3 Zahlen N, x und y die immer >=1.

N größer sein wird als x und y und x wird als y größer sein.

Jetzt müssen wir finden Sie die Summe aller Zahlen zwischen 1 und N, die durch x oder y teilbar sind.

kam ich mit auf den Punkt:

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

Gibt es eine Möglichkeit bessere Möglichkeit, die Summe der Suche nach der for-Schleife zu vermeiden?

Ich habe meinen Kopf seit vielen Tagen geschlagen, aber habe nichts besseres.

Wenn der Wert N eine obere Grenze hat, können wir eine Nachschlage-Methode verwenden, um den Prozess zu beschleunigen.

Danke an alle.

Ich wollte eine C/C++ basierte Lösung. Gibt es dafür eine eingebaute Funktion? Oder muss ich den Algorithmus programmieren?

Answer 1

Ja. Sie können die for-Schleife vollständig löschen und die Summe in konstanter Zeit finden.

die Inclusion–exclusion principle Nach dem mehrfachen von x und Multiples von y zusammen und präsentieren das gemeinsame Vielfache Subtraktion (n), die zweimal sollen uns die erforderliche Summe geben hinzugefügt wurde.

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) 

Beispiel:

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 

Wie oben gesehen, wir 12 abziehen mussten, da es zweimal hinzugefügt wurde, weil es ein gemeinsames Vielfaches ist.

Wie ist der gesamte Algorithmus O (1)?

Let sum(x, N) Summe von Vielfachen von x sein, die kleiner oder gleich 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 

Jetzt k = floor(N/x) kann in konstanter Zeit berechnet werden.

Sobald k bekannt ist sum(x,N) kann in konstanter Zeit berechnet werden.

So kann die erforderliche Summe auch in konstanter Zeit berechnet werden.

EDIT:

Die obige Diskussion gilt nur dann, wenn x und yco-primes sind.Wenn nicht, müssen wir LCM(x,y) anstelle von x*y verwenden. Es gibt viele Möglichkeiten, LCM zu finden, von denen eines ist, das Produkt durch GCD zu teilen. Jetzt kann GCD nicht in konstanter Zeit berechnet werden, aber seine time complexity kann wesentlich kleiner als die lineare Zeit gemacht werden.

Answer 2

Wenn eine Zahl durch X teilbar ist, muss sie ein Vielfaches von x sein. Wenn eine Zahl durch Y teilbar ist, muss sie ein Vielfaches von y sein.

Ich glaube, wenn Sie eine for-Schleife für alle Vielfachen von x und y, und vermeiden Sie alle Duplikate, sollten Sie die gleiche Antwort erhalten.

aus meinem Kopf, etwas von der Art:

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

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