Hallo zusammen,
ich muss für eine Statistik folgendes machen:
Ich habe ein Skript, dass liefert mir eine Liste von Restklassen. Beispielsweise [[1,4], [2,4], [1,3]]
Das bedeutet, dass alle Elemente k abgedeckt sind, für die gilt: k lässt bei Division durch 4 den Rest 1 oder 2. Oder k lässt bei Division durch 3 den Rest 1.
Nun möchte ich gerne ein Skript schreiben dass mir sagt, wieviele Restklassen noch übrig sind.
Mathematisch geht das folgendermaßen:
Bilde das kleinste gemeinsame Vielfache der Module (hier 3 und 4) und streiche alle abgedeckten Elemente.
Im obigen Beispiel also kgv = 12, und streiche nun
1,5,9
2,6,10
1 (bereits weg), 4,7, 10 (bereits weg)
Nun möchte ich in erster Linie wissen, wieviele Elemente übrig bleiben.
In meiner Statistik kommen teilweise kgv > eine Milliarde vor.
Trotzdem hatte ich gehofft, zumindest die gefragte Anzahl relativ schnell herauszubekommen.
Leider habe ich nun gar keine Ahnung, wie ich das mal angehen sollte.
Meine Idee war, über die Liste zu iterieren und in jedem Schritt das kgv zu bilden. Dann die Elemente streichen. Wenn dann im nächsten Schritt das kgv größer wird, würde ich die Liste mit dem >>Streichmuster<< einfach entsprechend oft hintereinanderhängen und dann bei den nicht-gestrichenen Elementen schauen, ob sie gestrichen werden müssen.
Ich bin nun absoluter Neuling und wollte euch daher um Hilfe bitten, in welche Richtung das geht. Auch wenn es fortgeschrittene Methoden wären (Bitvektor? Ich weiß nur dass es sowas gibt ), wäre ich sehr froh über Hilfestellung.
Vielen Dank an dieser Stelle für's Lesen