Armee

Maus Stofls Onkel Hans wurde zum Oberbefehlshaber der Armee von Käseland ernannt. Hans will möglichst schnell wissen, wie gross seine Armee ist. Bisher weiss er aber nur, dass die Anzahl Soldaten im Bereich von $A$ bis $B$ liegt.

Um die genaue Anzahl zu bestimmen, lässt er die gesamte Armee in Reihen à jeweils $x$ Soldaten einstehen und schaut jeweils wie viele Soldaten in der letzten Reihe übrig bleiben (eine Zahl zwischen $0$ und $x-1$).

Da nun die einzelnen Soldaten jeweils auf $x$ zählen müssen, um zu entscheiden, ob sie in einer Reihe noch Platz finden, dauert das Einstehen in $x$-er-Reihen Zeit $x$.

Falls nach dem Einstehen noch nicht klar ist, wie gross die Armee von Käseland ist, ruft Hans eine neue Zahl $y$ um die Soldaten umzuordnen. Die Soldaten stehen dann in Reihen à jeweils $y$ Soldaten ein, was wiederum Zeit $y$ dauert. Er wiederholt dies, bis er ganz sicher ist, wie viele Soldaten er befehligt.

Hilf Onkel Hans seine Armee so schnell wie möglich zu zählen.

Aufgabe

Gegeben zwei Zahlen $A$ und $B$, bestimme die optimalen Zahlen {$x,y,z,…$}, welche Stofl aufrufen muss, damit er die Soldaten eindeutig zählen kann und die Summe der gewählten Zahlen minimal ist.

Eingabe

Die Eingabe besteht aus einer einzelnen Zeile mit zwei Ganzzahlen $A$ und $B$ welche den Bereich der Armeegrösse beschreiben.

Ausgabe

Die Ausgabe besteht aus zwei Zeilen. Die erste Zeile enthält eine ganze Zahl $N$, die Anzahl gewählter Zahlen.

Auf der zweiten Zeile stehen diese $N$ Zahlen, jeweils getrennt durch ein Leerzeichen.

Beispiel

InputOutput

1 8

2
2 5

Natürlich könnte Hans einfach 8 rufen. Aber mit der Kombination von 2 und 5 lässt sich auch jede Anzahl zwischen 1 und 8 eindeutig unterscheiden und dies in nur 2+5=7 Zeiteinheiten statt 8.

Tipp

Bei der Recherche für Onkel Hans hat Maus Stofl herausgefunden, dass ein chinesischer Offizier seine Armee auch schon mit einer ähnlichen Methode zählte. Seine Methode ist in der Mathematik als 'Chinesischer Restsatz' bekannt.

Eine Erklärung in aller Kürze wie diese Methode funktioniert:

Genau wie Onkel Hans ruft der chinesische Offizier Zahlen, um seine Armee in entsprechende Reihen aufzustellen. Er ruft nur teilerfremde Zahlen und notiert sich die Anzahl der Soldaten in der hintersten Reihe.

Beispiel:

Wir suchen die Anzahl Soldaten x wie folgt:

3-er-Reihe: 1 Soldat bleibt übrig

4-er-Reihe: 3 Soldaten bleiben übrig

5-er-Reihe: 2 Soldaten bleiben übrig

Wir können auch sagen, dass die Zahl der Soldaten $x$ bei der Division durch 3 den Rest 1 ergibt bzw. dass $x$ modulo 3 gleich 1 ist. Man schreibt «$x = 1$ mod $3$» und nennt eine solche Gleichung eine Kongruenz.

$3$, $4$ und $5$ sind offensichtlich teilerfremd. Wir benennen nun die Reihengrössen $m_1=3, m_2=4, m_3=5$ und die Reste $r_1=1, r_2=3, r_3=2$.

Zudem wählen wir $m=kgV(m_1,…,m_n)=\Pi_{i=1}^{n}{m_i}=m_1*m_2*m_3=3*4*5=60$.

Der chinesische Restsatz sagt nun aus, dass im Bereich von $0$ bis $m-1$ jede Zahl eine unterschiedliche Kombination von Resten $r_1, …, r_n$ ergibt.

Nun schauen wir an, wie wir aus den $m_i$ und $r_i$ auf ein eindeutiges $x$ schliessen können. Dazu berechnen wir zuerst $M_i = m/m_i$, also in unserem Beispiel: $M_1=20, M_2=15, M_3=12$.

Als nächstes folgt der mathematisch anspruchsvollste Teil: wir ermitteln die multiplikativen Inversen der $M_i$ modulo $m_i$. Das heisst wir suchen Zahlen $y_i$ sodass $y_i*M_i = 1$ mod $m_i$.

Um diese Inversen zu berechnen gibt es einen Algorithmus der 'erweiterter euklidischer Algorithmus' heisst, der aber hier nicht weiter erklärt werden muss. Für unser einfaches Beispiel können wir die Inversen auch durch Ausprobieren finden:

Es ist $y_1 = 2$, weil $2*20 = 40$ was modulo 3 gleich $40 - 13*3 = 1$ ist.

Analog sind $y_2 = 3$, da $3*15$ modulo 4 gleich $45 - 11*4 = 1$ ist

und $y_3= 3$, da $3*12$ modulo 5 gleich $36 - 7*5 = 1$ ist.

Somit haben wir alle nötigen Zutaten beisammen, die wir für die Berechnung von $x$ verwenden werden. Nun gilt nämlich:

$x = \sum_{i=1}^{n}(r_i*y_i*M_i)$ mod $m$.

In unserem Beispiel bedeutet dies, dass wir $x$ wie folgt berechnen können:

$x=(1*2*20 + 3*3*15 + 2*3*12)$ mod 60 = 247 mod 60 = 7.

Hier befehligt der chinesische Offizier also 7 Soldaten.

Zusammengefasst bedeutet dies, dass wir nach dem Aufrufen einer Menge von teilerfremden Zahlen anschliessend alle Zahlen in einem Bereich von 0 bis (zum kleinsten gemeinsamen Vielfachen dieser Zahlen - 1) eindeutig unterscheiden können.

Weitere Ausführungen zum chinesischen Restsatz und zum erweiterten euklidischen Algorithmus findest du hier:

Chinesischer Restsatz in der deutschen Wikipedia:

http://de.wikipedia.org/wiki/Chinesischer_Restsatz

Informatikdepartement der FH Flensburg über den chinesischen Restsatz:

http://www.inf.fh-flensburg.de/lang/krypto/algo/chinese-remainder.htm

Erweiterter Euklidischer Algorithmus in der deutschen Wikipedia:

http://de.wikipedia.org/wiki/Erweiterter_Euklidischer_Algorithmus

Einsendung