Somme de la série: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)

Quelqu'un peut-il me donner une idée d'un algorithme efficace pour n grand (disons 10^10) pour trouver la somme de la série ci-dessus?

Mycode est arriver klilled pour n= 100000 et 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);

}
u peut utiliser java?
L'aviateur: algorithmes Efficaces sont généralement indépendants de la langue. Ne devrait pas vraiment d'importance si c'est Java ou C (à l'exception peut-être un facteur linéaire dans l'exécution).
Je comprends. J'ai pensé à ce qui suggère BigInteger. C'est pourquoi demandé
Vous dites que vous voulez quelque chose de rapide pour big n (10^10), mais vous ne dites pas si m est de même taille, ou si elle reste autour de 200k. Il peut d'importance, parce que si m est petit, alors vous pouvez essayer de pré-calcul/la mise en cache de certains termes. Si vous connaissez déjà un^m^a pour tous les moins de m, alors quand vous venez à calculer (m+2)^(m+2) ensuite, c'est juste 2^(m+2) = 2^m*2^2. Alors (m+3)^(m+3) = 3^m*3^3 et ainsi de suite. Vous pouvez probablement arranger les choses pour vous que vous avez toujours accès à vos valeurs stockées séquentiellement, pas sûr.
Penser à ce sujet, vous pouvez également le cache de 1^2m ... (m-1)^2m ainsi, alors que vous êtes le calcul de la 2m+1 ... 3m-1 termes. Utilisez ces valeurs pour calculer 1^3m ... (m-1)^3 m, et de remplacer la valeur stockée avec la nouvelle valeur pour le calcul de 1^4m ... (m-1)^4m. Sans écrire le code que j'ai aucune idée si ce sera effectivement plus rapide que Mehrdad de solutino, mais à moins que j'ai raté quelque chose de fatal, c'est O(n) au lieu de O(n log n). Il faut, évidemment, O(m) de la mémoire.

OriginalL'auteur | 2009-10-01

  1. 23

    Deux remarques:

    (a + b + c) % m

    est équivalent à 

    (a % m + b % m + c % m) % m

    et

    (a * b * c) % m

    est équivalent à

    ((a % m) * (b % m) * (c % m)) % m

    Comme un résultat, vous pouvez calculer chaque terme à l'aide d'une fonction récursive en 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;
}

    Et la somme des éléments à l'aide d'un for boucle:

    long long r = 0;
for (int i = 1; i <= n; ++i)
    r = (r + expmod(i, i, m)) % m;

    Cet algorithme est O(n journal n).

    Pour les petits nombres, je suis en train de faire la même chose. Mais il se fait tué par n = 1000000 et m =200000 . J'ai inclus le code
    Je crois que vous avez besoin d'un autre mod' dans les équations: '(% m + b % m + c % m) % m', et '(% m) * (b % m) * (c % m) % m'.
    Groo: Yep, le fait que dans le code, oubliée dans les équations. Merci. Fixe.
    Votre intérieur j-boucle s'exécute en O(i). Mehrdad de la fonction s'exécute en O(log i). Remplacer votre boucle interne par un appel à Mehrdad fonction et vous obtiendrez une grande vitesse.
    Dans le cas de n=1000 m=2000, suite 1000^1000%de 2000 à (1000^2%2000)^500%2000.

    OriginalL'auteur Mehrdad Afshari

  2. 5

    Je pense que vous pouvez utiliser le théorème d'Euler pour éviter certains exponentation, phi phi(200000)=80000. Théorème des restes chinois pourrait aussi aider, car elle réduit le modulo.

    Cela ne dit quelque chose, mais je crains que vous aurez à expliquer. Aussi, autant que je me souvienne, le calcul de phi n'est pas trivial.
    Vous avez besoin de calculer phi qu'une seule fois. Le théorème d'Euler dit qu'un^phi(b)=1 mod b si (a,b)=1. Ensuite, vous pouvez simplifier un^c mod b de la forme a^c' mod b où c'<phi(b).
    Jaska: C'est sans importance ici. Que faire si (a,b) != 1?
    Pointe - essayez de modifier votre réponse. Élaborer. Décrire et expliquer votre algorithme suggéré. Essayer de poster un peu de code. Lien vers Wikipédia. Aussi, n'est-ce pas le théorème des restes Chinois utilisé pour un ensemble d'équations?
    Le théorème d'Euler et Chinois rappel théorème sont faciles à regarder, et ils sont tous les deux (en collaboration) parfaitement pertinente ici — utiliser le théorème d'Euler pour calculer la somme mod chaque premier pouvoir en m, et l'utilisation CRT pour les mettre ensemble.

    OriginalL'auteur

  3. 3

    Vous pouvez avoir un coup d'oeil à ma réponse à ce post. La mise en œuvre il y a un peu buggé, mais l'idée est là. La stratégie clé est de trouver x tel que n^(x-1)<m et n^x>m et à plusieurs reprises de réduire les n^n%m à (n^x%m)^(n/x)*n^(n%x)%m. Je suis sûr que cette stratégie fonctionne.

    OriginalL'auteur user172818

  4. 1

    J'ai rencontré la même question récemment: mon " n " est en 1435, 'm' est de 10^10. Voici ma solution (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;
}

    À la fin " s " est égal au nombre requis.

    OriginalL'auteur Rail Suleymanov

  5. 0

    Êtes-vous tué ici:

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

    Exponentielles mod m pourraient être mises en œuvre à l'aide de la somme des carrés de la méthode.

    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;
}

    OriginalL'auteur Calyth

  6. 0

    Je ne peux pas ajouter de commentaire, mais pour le théorème des restes Chinois, voir http://mathworld.wolfram.com/ChineseRemainderTheorem.html les formules (4)-(6).

    Je ne vois pas comment cela aide

    OriginalL'auteur Jaska