Nun, nachdem ich dieses Problem durch naives STL-Set gelöst hatte, las ich die Foreneinträge , da finde ich diesen Eintrag:
%Vor% Die Erklärung des Autors:
Maximum will be 99*99. I subtracted occurrences of those numbers which are powers of some lower numbers (2-100): -
For example: -
4^2,4^3,4^4 (i.e. 3 should be subtracted) as they will be duplicates from lower number powers as in 2^4,2^6,2^8
Dieses Programm gibt die richtige Antwort hier überprüfen , aber ich bin nicht in der Lage, die implementierte Logik zu bekommen, um genau zu sein, die ich nicht bekomme wie die Duplikate bestimmt sind. Könnte jemand helfen?
Ich vermisse etwas, aber es scheint mir, dass dieses Programm die falsche Antwort gibt. Es geht um eins. Wenn ich MAX auf 10 setze, ist es um zwei.
Ich habe gelesen, dass einige Spieler ungefähre Antworten produzieren und dann die Projekt-Euler-Server angreifen, um das Problem brutal zu erzwingen. Andere Spieler denken das eher gegen den Geist der Sache.
Wie auch immer - ein Algorithmus wie dieser (beginnend mit N * M und Eliminierung von Duplikaten) ist der richtige Weg, um das Problem anzugehen, aber wie geschrieben, macht dieser Code für mich keinen Sinn. Beachten Sie, dass int(MAX*(log(i)/log(j))) in jedem Fall sehr empfindlich auf Rundungsfehler reagiert. Aber selbst wenn Sie diese Fehlerquelle mit Ganzzahlarithmetik eliminieren, gibt das Programm immer noch die falsche Antwort.
BEARBEITEN: Wie können wir die Duplikate (korrekt) zählen?
Zunächst müssen Sie verstehen, dass zwei Zahlen nur dann gleich sind, wenn sie die gleiche Primfaktorzerlegung haben. Es gibt also nur Dubletten a 1 b 1 = a 2 b 2 wenn a 1 und a 2 sind verschiedene ganzzahlige Potenzen derselben Ganzzahl, die ich x nennen werde. Zum Beispiel
Wir haben also festgestellt, dass für alle Duplikate a 1 = x e 1 und a 2 = x e 2 für einige Ganzzahlen x , e 1 und e 1 .
Dann mit ein wenig Algebra,
a 1 b 1 = a 2 b 2
x e 1 b 1 = x e 2 b 2
e 1 b 1 = e 2 b 2
Zurück zu den früheren Beispielen,
Um also alle Duplikate für jedes gegebene x zu finden, müssen Sie nur Duplikate für den einfacheren Ausdruck eb finden, wobei 2 ≤ x
Hier ist ein Bild dieses einfacheren Problems, für x = 3 und b von nur 2 bis 10. Ich habe zwei Stellen markiert, an denen Duplikate vorhanden sind.
%Vor%Und hier sind die Duplikate:
%Vor%Das C ++ - Programm, das Sie gefunden haben, versucht, sie zu zählen, indem es jedes Paar überlappender Zeilen i und j besucht und berechnet, wie viel von Zeile i die Zeile j überlappt. Aber auch wenn ich etwas verpasse, scheint das Programm hoffnungslos ungenau. Und es fehlen einige Paare von Zeilen vollständig (Sie haben nie i = 9 und j = 27 oder i = 27 und j = 81).
Zuerst setzt es res auf 99 * 99 in Zeile 6, weil MAX als 100 definiert wurde. Dann tritt es in eine Schleife ein, mit der Bedingung, dass i kleiner als MAX ist. dann tritt es in diese Pseudocode-Schleife ein
für (j = i 2 ; j <= MAX, j = i x )
{
res = res- (MAX * ( j log (i)) +1;
x ++;
}
Entschuldigung, dass <pre><code> oben nicht verwendet wurde; aber wenn ich das tat, konnte ich <sup>
Bitte beachten Sie log(a)/log(x) ist das gleiche wie x log (a)
kommentiert die Frage, weil <sup> dort nicht funktioniert:
2 log (2) = 1, weil 2 1 = 2 (2) 2 log (4) = 2 weil 2 2 = 2
log (x) == 10 log (x)
log (10) = 1
g log (x) = y = & gt; g y = x
Nun, die Frage beinhaltet Möglichkeiten, zwei Zahlen aus einem Bereich zu kombinieren. Es gibt 99 mögliche Zahlen, die Anzahl der Kombinationen ist 99 * 99, mit möglichen Duplikaten. Sein grundlegender Algorithmus besteht darin, herauszufinden, wie viele Duplikate vorhanden sind, und diesen Wert vom Maximum zu subtrahieren.
Was das Zählen von Duplikaten betrifft, könnte es intuitiv helfen, die Zahlen in Bezug auf ihre Primfaktoren zu denken. Eine Zahl auf eine ganzzahlige Potenz zu erhöhen bedeutet, sie selbst zu multiplizieren; also, als eine Liste von Primzahlen dargestellt, ist dies gleichbedeutend mit der einfachen Verkettung der Listen. Zum Beispiel ist 6 {2, 3}, also wäre 6 ^ 3 {2, 2, 2, 3, 3, 3}. Beachten Sie, dass, wenn Sie zählen, wie oft jede Primzahl in der Liste erscheint, x ^ n immer die gleichen Proportionen wie x hat, zum Beispiel 6 ^ n wird eine gleiche Menge an 2er und 3er haben. Also müssen zwei beliebige Zahlen im Bereich mit dem gleichen Verhältnis zwischen Primzahlen beide Potenzen einer Zahl sein.
Also wird in der vollständigen Liste jedes einzelne Verhältnis von Primfaktoren wiederholt als x ^ 2, x ^ 3, x ^ 4 ..., (x ^ 3) ^ 2, (x ^ 3) ^ 4 erscheinen ..., (x ^ 4) ^ 2 ... usw., wobei x die kleinste Zahl mit diesem Anteil ist; genauer gesagt, (x ^ m) ^ n wobei (x ^ m) & lt; = 100 und 2 & lt; = n & lt; = 100. Da (x ^ m) ^ n ist gleich x ^ (m n ), das Zählen von Duplikaten zählt zum Zählen der Möglichkeiten, dass x ^ (m n) auch & lt; = 100 sein kann.
Es gibt (mindestens) zwei Möglichkeiten, dieses Problem anzugehen. Eine besteht darin, die Anzahl eindeutiger Werte bei 0 zu beginnen und für jeden berechneten Wert einen Wert zu addieren, der zuvor nicht gesehen wurde. Die andere Möglichkeit besteht darin, die maximale Anzahl von Werten zu berechnen und dann für jedes Duplikat eins zu subtrahieren.
Das Poster versucht das zweite methed. a kann für 99 Werte von 2 bis 100 reichen, ebenso wie b , also gibt es 99 * 99 produzierte Werte. Das Poster versucht dann, die doppelten Werte zu subtrahieren, um die richtige Antwort zu erhalten.
Bearbeiten: Das Poster hat jedoch einen falschen Algorithmus geschrieben.
Setzen Sie beispielsweise MAX = 8 oder 9 . Für 8 sollte 44 angegeben werden, aber es gibt 45 . Für 9 sollte 54 angegeben werden, aber 56 . Entweder hatten sie Glück und passierten einen Algorithmus, der für einige Eingaben die richtige Antwort lieferte, oder sie entwickelten einen Algorithmus, der bei MAX = 100 , aber nicht bei allen anderen Werten funktionierte.