Problem
Betrachte positive ganze Zahlen strikt unterhalb des Limits. Ein Wert wird einbezogen, wenn er durch mindestens einen von null verschiedenen Faktor teilbar ist. Jeder einbezogene Wert wird nur einmal gezählt, auch wenn er durch mehrere Faktoren teilbar ist. Faktoren mit dem Wert null werden ignoriert. Die Faktoren [3, 5] ergeben die bekannte Aufgabe der Vielfachen von 3 oder 5.
Implementiere sum_of_multiples(limit, factors).
Eingabe
limit: Die exklusive obere Grenze.
factors: Die Faktoren, deren Vielfache berücksichtigt werden.
Ausgabe
Gib die Summe der unterschiedlichen, berechtigten positiven ganzen Zahlen zurück.
Einschränkungen
0 ≤ limit ≤ 100.000. Es kann 0 bis 20 Faktoren geben, jeder zwischen 0 und 100.000. Doppelte Faktoren sind erlaubt.
Beispiele
Eingabe:
limit = 12
factors = [3, 5]
Erwartete Ausgabe:
expected = 33Eingabe:
long long limit = 12;
std::vector<long long> factors = {3, 5};
Erwartete Ausgabe:
long long expected = 33;Eingabe:
long limit = 12;
long[] factors = new long[] {3, 5};
Erwartete Ausgabe:
long expected = 33;Erläuterung
Die einbezogenen Werte sind 3, 5, 6, 9 und 10. Ihre Summe ist 33.
Eingabe:
limit = 10
factors = [2, 4]
Erwartete Ausgabe:
expected = 20Eingabe:
long long limit = 10;
std::vector<long long> factors = {2, 4};
Erwartete Ausgabe:
long long expected = 20;Eingabe:
long limit = 10;
long[] factors = new long[] {2, 4};
Erwartete Ausgabe:
long expected = 20;Erläuterung
Beziehe 2, 4, 6 und 8 ein. Die Werte 4 und 8 werden nur einmal gezählt, obwohl sie zu beiden Faktoren passen.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Nur Werte, die durch mindestens einen nutzbaren Faktor teilbar sind, sollen einmal beitragen.
Hinweis 2
Nutze das Inklusions-Exklusions-Prinzip, um überlappende Vielfache ohne Doppelzählung zu kombinieren.
Hinweis 3
Ignoriere Null-Faktoren und Duplikate, bevor du rechnest.
Erwartete Komplexität
Zeit O(2^m), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.