Ich mache eine (für mich selbst) sehr komplexe Aufgabe, bei der ich die größtmögliche Anzahl von Folgen berechnen muss, wenn man eine Anzahl n von Segmenten angibt.
Ich fand heraus, dass die katalanische Zahl diese Sequenzen darstellt, und ich habe es für n & lt; = 32 funktionieren lassen. Die Ergebnisse, die ich bekomme, sollten mit 1.000.000.007 berechnet werden. Das Problem, das ich habe, ist, dass "q" und "p" für eine lange lange int zu groß werden und ich kann nicht einfach mod 1.000.000.007 vor dem Teilen von "q" und "p", weil ich ein anderes Ergebnis bekommen würde.
Meine Frage ist, gibt es eine wirklich effiziente Möglichkeit, mein Problem zu lösen, oder muss ich darüber nachdenken, die Werte anders zu speichern? Meine Einschränkungen sind die folgenden: - nur stdio.h / iostream - Nur ganze Zahlen - n & lt; = 20.000.000 - n & gt; = 2
%Vor%Um dies effizient zu lösen, sollten Sie modulare Arithmetik verwenden, mit modulare Inverses ersetzen die Division.
Es ist einfach zu beweisen, dass in Abwesenheit von Überlauf (a * b) % c == ((a % c) * b) % c . Wenn wir nur multiplizieren würden, könnten wir die Ergebnisse mod 1000000007 bei jedem Schritt nehmen und immer innerhalb der Grenzen einer 64-Bit-Ganzzahl bleiben. Das Problem ist die Teilung. (a / b) % c entspricht nicht unbedingt ((a % c) / b) % c .
Um das Problem mit der Division zu lösen, verwenden wir modulare Inverse. Für Ganzzahlen a und c mit c prime und a % c != 0 können wir immer eine Ganzzahl b finden, so dass a * b % c == 1 . Dies bedeutet, dass wir Multiplikation als Division verwenden können. Für jede Ganzzahl d teilbar durch a , (d * b) % c == (d / a) % c . Dies bedeutet, dass ((d % c) * b) % c == (d / a) % c , so dass wir die Zwischenergebnisse mod c reduzieren können, ohne unsere Fähigkeit zu teilen, zu teilen.
Die Zahl, die wir berechnen möchten, hat die Form (x1 * x2 * x3 * ...) / (y1 * y2 * y3 * ...) % 1000000007 . Wir können stattdessen x = x1 % 1000000007 * x2 % 1000000007 * x3 % 1000000007 ... und y = y1 % 1000000007 * y2 % 1000000007 * y3 % 1000000007 ... berechnen und dann die modulare inverse z von y mit dem erweiterten euklidischen berechnen Algorithmus und return (x * z) % 1000000007 .
Wenn Sie gcc oder clang und ein 64-Bit-Ziel verwenden, gibt es einen __int128-Typ . Das gibt Ihnen zusätzliche Bits, mit denen Sie arbeiten können, aber offensichtlich nur zu einem bestimmten Punkt.
Sehr wahrscheinlich ist der einfachste Weg, um mit dieser Art von Problem umzugehen, die Verwendung einer "bignum" -Bibliothek, d. h. einer Bibliothek, die sich mit dem Darstellen und Ausführen von Arithmetik an beliebig großen Zahlen beschäftigt. Das wohl populärste Open-Source-Beispiel ist libgmp - Sie sollten damit in der Lage sein, Ihren Algorithmus relativ einfach zu nutzen. Es ist auch auf hohe Leistungsstandards abgestimmt.
Natürlich können Sie das selbst re-implementieren, indem Sie Ihre Zahlen als z. Arrays von ganzen Zahlen einer bestimmten Größe. Sie müssen Algorithmen für die Grundrechenarten wie +, -, *, /,% selbst implementieren. Wenn Sie dies als Lernerfahrung tun möchten, ist das in Ordnung, aber es ist keine Schande, libgmp zu verwenden, wenn Sie sich nur auf den Algorithmus konzentrieren möchten, den Sie implementieren möchten.
Tags und Links c performance store division modulo