Berechnung 1^X + 2^X + ... + N^X mod 1000000007

Gibt es einen Algorithmus zur Berechnung (1^x + 2^x + 3^x + ... + n^x) mod 1000000007?
Hinweis: a^b ist die b-te Potenz von a.Berechnung 1^X + 2^X + ... + N^X mod 1000000007

Die Einschränkungen sind 1 <= n <= 10^16, 1 <= x <= 1000. Also ist der Wert von N sehr groß.

Ich kann nur für O(m log m) lösen, wenn m = 1000000007. Es ist sehr langsam, weil das Zeitlimit 2 Sekunden beträgt.

Haben Sie einen effizienten Algorithmus?

Es gab einen Kommentar, dass es ein Duplikat von this question sein könnte, aber es ist definitiv anders.

Quelle

2017-01-17 square1001

@ TobySpeight Nein, es ist definitiv anders. 1^x, 2^x ..., n^x ist mod exponentiell, und ich möchte SCHNELLER ALGORITHMUS finden, weil n <= 10^16 und mod = 10^9 + 7. – square1001

n^x mod m ist das gleiche wie ((n^(x-1) mod m) * (n mod m)) mod m; (a + b) mod m ist das gleiche wie ((a mod m) + (b mod m)) mod m. – Vatine

@TobySpeight In meinem langsamen Algorithmus muss ich mod etwa 10^10 mal nehmen. Aber es ist sehr langsam, weil das Zeitlimit 2 Sekunden beträgt. Ich möchte nur schnellen Algorithmus finden. – square1001

Sie können Summe bis die Serie

mit Hilfe von Faulhaber's formula und Sie werden ein Polynom mit einem X + 1 Macht bekommen für beliebige N zu berechnen.

Wenn Sie nicht Bernoulli-Zahlen berechnen möchten, können Sie das das Polynom finden durch X + 2lineare Gleichungen zu lösen (für N = 1, N = 2, N = 3, ..., N = X + 2), die eine langsamere Methode ist aber einfacher zu implementieren.

Lassen Sie uns ein Beispiel für X = 2 haben. In diesem Fall haben wir ein X + 1 = 3 Polynom:

A*N**3 + B*N**2 + C*N + D

Die linearen Gleichungen

 A + B + C + D = 1    = 1 
    A*8 + B*4 + C*2 + D = 1 + 4   = 5 
    A*27 + B*9 + C*3 + D = 1 + 4 + 9  = 14 
    A*64 + B*16 + C*4 + D = 1 + 4 + 9 + 16 = 30

Nachdem gelöst, die Gleichungen sind wir

A = 1/3 
    B = 1/2 
    C = 1/6 
    D = 0

Die endgültige Formel erhalten ist

1**2 + 2**2 + ... + N**2 == N**3/3 + N**2/2 + N/6

Nun müssen Sie lediglich einen beliebig großenN in die Formel einfügen. Bisher hat der Algorithmus O(X**2) Komplexität (da es nicht auf N angewiesen ist).

Quelle

2017-01-17 11:41:20

Aber leider könnte x 1000 sein ... Die lineare Gleichung kann O (X^3) sein, aber ich denke, es ist langsam. Ich schaue gerade nach Faulhabers Formel. – square1001

@ square1001: Wenn Sie sehr schnell sein müssen, empfehle ich vorberechnen * Bernoulli Zahlen * (bis zu '1000'); Es ist keine leichte Aufgabe (wie lineare Gleichungen lösen), aber in diesem Fall erhalten Sie das Polynom fast fertig zu verwenden. –

Ich überprüfte Bernoulli-Nummer und verstand schließlich, dass B [1], B [2], ..., B [x] für O (x^2). Also kann dieses Problem für O (N^2) lösen! – square1001

Es gibt einige Möglichkeiten, die modulare Potenzierung zu beschleunigen. Von hier an werde ich ** verwenden, um "potenzieren" und % zu bezeichnen, um "Modul" zu bezeichnen.

Zuerst ein paar Beobachtungen. Es ist immer der Fall, dass (a * b) % m((a % m) * (b % m)) % m ist. Es ist auch immer der Fall, dass a ** n dasselbe ist wie (a ** floor(n/2)) * (a ** (n - floor(n/2)). Dies bedeutet, dass wir für einen Exponenten < = 1000 die Potenzierung immer in höchstens 20 Multiplikationen (und 21 Mods) vervollständigen können.

Wir können auch einige Berechnungen überspringen, da (a ** b) % m das gleiche wie ((a % m) ** b) % m ist und wenn m deutlich niedriger als n ist, haben wir einfach mehrere sich wiederholende Summen, mit einem "Schwanz" einer partiellen Wiederholung.

Quelle

2017-01-17 11:19:04 Vatine

Aber Ihr Algorithmus muss 1^x, 2^x, ..., 1000000006^x berechnen. Es hat mehr als 10^9 Terme, also müssen Sie über 10^10 mal iterieren. Also, ich denke, es kann nicht passieren, weil das Zeitlimit 2 Sekunden beträgt. – square1001

@ square1001 Habe gerade eine NOP-Schleife auf meinem Laptop getestet, dauert ~ 0,1 Sekunden, um 10 ** 10 Mal zu iterieren und das wird wahrscheinlich von "fork" und "exec" dominiert. – Vatine

Dies wird * viel * einfacher, wenn * x * ungerade ist, weil zum Beispiel '1000000006' kongruent zu' -1' ist, also '1^x' und' 1000000006^x' ausgleichen, und so viele andere Begriffe. Ich sehe keine Verknüpfung, wenn * x * gerade ist. –

Ich denke, Vatine Antwort ist wahrscheinlich der Weg zu gehen, aber ich tippte bereits dies und es kann nützlich sein, für dieses oder für jemand anderes ähnliche Problem.

Ich habe heute Morgen keine Zeit für eine detaillierte Antwort, aber denke darüber nach. 1^2 + 2^2 + 3^2 + ... + n^2 würde O (n) Schritte, um direkt zu berechnen. Es entspricht jedoch (n(n+1)(2n+1)/6), die in O (1) Zeit berechnet werden kann. Eine ähnliche Äquivalenz existiert für jede höhere integrale Leistung x.

Es mag eine allgemeine Lösung für solche Probleme geben; Ich kenne keinen, und Wolfram Alpha scheint auch keinen zu kennen. Jedoch in allgemein der äquivalente Ausdruck ist Grad x + 1, und kann heraus bearbeitet werden, indem einige Beispielwerte berechnet werden und ein Satz linearer Gleichungen für die Koeffizienten gelöst wird.

Dies wäre jedoch schwierig für große x, wie 1000 als in Ihrem Problem, und wahrscheinlich nicht innerhalb von 2 Sekunden getan werden konnte.

Vielleicht kann jemand, der mehr Mathematik als ich weiß, dies in eine praktikable Lösung verwandeln?

Edit: Whoops, ich sehe Fabian Pijcke hatte bereits einen nützlichen Link über Faulhaber's formula gepostet, bevor ich gepostet habe.

Quelle

2017-01-17 11:27:57

Berechnung 1^X + 2^X + ... + N^X mod 1000000007

Antwort

Verwandte Themen