Summe der Reihe: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)

Kann mir jemand eine Idee für einen effizienten Algorithmus für großes n (etwa 10^10) zu finden, die Summe der oben genannten Serie?

Mycode ist immer klilled für n= 100000 und m=200000

#include<stdio.h>

int main() {
    int n,m,i,j,sum,t;
    scanf("%d%d",&n,&m);
    sum=0;
    for(i=1;i<=n;i++) {
        t=1;
        for(j=1;j<=i;j++)
            t=((long long)t*i)%m;
        sum=(sum+t)%m;
    }
    printf("%d\n",sum);

}

kann u verwenden Sie java?
Aviator: Effiziente algorithmen sind in der Regel unabhängig von der Sprache. Sollte nicht wirklich eine Rolle, ob diese in Java, oder C (ausser vielleicht ein linearer Faktor in der Laufzeit).
Ich verstehe. Ich dachte, der darauf hindeutet, BigInteger. Thats, warum gefragt
Sie sagen, Sie wollen etwas schnelles für große n (10^10), aber Sie nicht sagen, ob m ist ebenso groß, oder wenn es bleibt etwa 200k. Es ist vielleicht auch egal, denn wenn m klein ist, dann können Sie versuchen, pre-Berechnung/caching einige Begriffe. Wenn Sie bereits wissen, a^m^a für alle a kleiner als m, dann wenn Sie kommen, um zu berechnen, (m+2)^(m+2), dann ist es nur 2^(m+2) = 2^m*2^2. Dann (m+3)^(m+3) = 3^x*3^3 und so weiter. Sie können wahrscheinlich Dinge so anzuordnen, dass Sie immer Zugriff auf Ihre gespeicherten Werte nacheinander, nicht sicher.
Denken Sie daran, Sie möchten vielleicht auch cache 1^2m ... (m-1)^2m als auch, während, du bist der Berechnung der 2m+1 ... 3m-1 Bedingungen. Dann verwenden Sie diese Werte zur Berechnung 1^3m ... (m-1)^3m, und ersetzen Sie den gespeicherten Wert mit dem neuen Wert für die Verwendung in der Berechnung von 1^4 m ... (m-1)^4m. Ohne den code zu schreiben ich habe keine Ahnung, ob das tatsächlich schneller sein, als Mehrdad ist solutino, aber es sei denn, ich habe etwas verpasst fatal, es ist O(n) statt O(n log n). Offensichtlich erfordert O(m) Speicher obwohl.

InformationsquelleAutor | 2009-10-01

algorithm series

23

Zwei Hinweise:
```
(a + b + c) % m
```
entspricht
```
(a % m + b % m + c % m) % m 
```
und
```
(a * b * c) % m
```
entspricht
```
((a % m) * (b % m) * (c % m)) % m
```
Als Ergebnis, können Sie berechnen jeden term mit einer rekursiven Funktion in O(log p):
```
int expmod(int n, int p, int m) {
   if (p == 0) return 1;
   int nm = n % m;
   long long r = expmod(nm, p /2, m);
   r = (r * r) % m;
   if (p % 2 == 0) return r;
   return (r * nm) % m;
}
```
Und die Summe der Elemente mit einem for Schleife:
```
long long r = 0;
for (int i = 1; i <= n; ++i)
    r = (r + expmod(i, i, m)) % m;
```
Dieser Algorithmus ist O(n log n).

Für kleine zahlen, die ich Tue die gleiche Sache. Aber es wird immer getötet, für n = 1000000 und m =200000 . Ich habe den code
Ich glaube, Sie brauchen noch eine 'mod' in diesen Gleichungen: '(a % m + b % m + c % m) % m', und '(a % m) * (b % m) * (c % m) % m'.
Groo: Ja, hab das im code, verpasste in Gleichungen. Danke. Behoben.
Ihre innere j-Schleife läuft in O(i). Mehrdad Funktion läuft in O(log ich). Ersetzen Sie Ihre innere Schleife durch einen Aufruf von Mehrdad Funktion und erhalten Sie einen großen speed-up.
Im Falle von n=1000 und m=2000, Ergebnis 1000^1000%2000(1000^2%2000)^500%2000.

InformationsquelleAutor Mehrdad Afshari
5

Ich denke, dass Sie verwenden können, Euler ' s theorem zu vermeiden, dass einige exponentation, als phi(200000)=80000. Chinesischen Rest-Satz könnte auch helfen, denn Sie reduziert modulo.

Dies bedeutet ring Glocken, aber ich fürchte, das musst du mal erklären. Auch, wenn ich mich Recht erinnere, computing phi ist nicht trivial.
Sie müssen berechnen Sie phi nur einmal. Das Eulersche theorem besagt, dass a^phi(b)=1 mod b, wenn (a,b)=1. Dann können Sie vereinfachen,^c mod b der form a^c' mod b, wo c'<phi(b).
'Jaska: Es ist hier irrelevant. Was ist, wenn (a,b) != 1?
Tipp - versuchen Sie, Bearbeiten Sie Ihre Antwort. Aufwendige. Beschreiben und erklären Sie die von Ihnen vorgeschlagenen Algorithmus. Versuchen Sie zu posten von code. Link zu Wikipedia. Auch nicht die chinesischen Rest-Satz, verwendet für einen Satz von Gleichungen?
Euler-theorem und Chinese reminder theorem sind einfach zu suchen, und Sie sind beide (zusammen) perfekt hier relevant — die Verwendung von Euler-theorem zur Berechnung der Summe mod jedes prime power in m, und verwenden CRT zusammenzusetzen.

InformationsquelleAutor
3

Können Sie einen Blick auf meine Antwort auf dieser Beitrag. Die Umsetzung ist es etwas buggy, aber die Idee ist da. Der Schlüssel Strategie ist die Suche x, so dass n^(x-1)<m und n^x>m und wiederholt reduzieren n^n%m (n^x%m)^(n/x)*n^(n%x)%m ist. Ich bin sicher, dass diese Strategie funktioniert.

InformationsquelleAutor user172818

Traf ich ähnliche Frage vor kurzem: meine 'n' 1435, 'm' ist 10^10. Hier ist meine Lösung (C#):

ulong n = 1435, s = 0, mod = 0;
mod = ulong.Parse(Math.Pow(10, 10).ToString());
for (ulong i = 1; i <= n; 
{
     ulong summand = i;
     for (ulong j = 2; j <= i; j++)
     {
         summand *= i;
         summand = summand % mod;
     }
     s += summand;
     s = s % mod;
}

Ende 's' ist gleich der erforderlichen Anzahl.

InformationsquelleAutor Rail Suleymanov

Sind Sie immer getötet hier:

for(j=1;j<=i;j++)
    t=((long long)t*i)%m;

Exponentialfunktionen mod m umgesetzt werden könnte mit der Summe der Quadrate Methode.

n = 10000;
m = 20000;
sqr = n;
bit = n;
sum = 0;

while(bit > 0)
{
    if(bit % 2 == 1)
    {
        sum += sqr;
    }
    sqr = (sqr * sqr) % m;
    bit >>= 2;
}

InformationsquelleAutor Calyth

0

Kann ich nicht kommentieren, aber für den chinesischen Rest-theorem, siehe http://mathworld.wolfram.com/ChineseRemainderTheorem.html Formeln (4)-(6).

Ich kann nicht sehen wie das hilft

InformationsquelleAutor Jaska

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.