Somme des séries: 1 ^ 1 + 2 ^ 2 + 3 ^ 3 + ... + n ^ n (mod m)
Question
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 de se klilled pour n = m = 100000 et 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);
}
La solution
Deux notes:
(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
Par conséquent, vous pouvez calculer chaque terme en utilisant 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 les éléments de somme en utilisant une boucle de for
:
long long r = 0;
for (int i = 1; i <= n; ++i)
r = (r + expmod(i, i, m)) % m;
Cet algorithme est O ( n log n ).
Autres conseils
Je pense que vous pouvez utiliser le théorème d'Euler pour éviter certains exponentation, comme phi (200000) = 80000. théorème chinois pourrait aussi aider, car il réduit le modulo.
Vous pouvez jeter un oeil à ma réponse ce poste . 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)
Je rencontrais récemment question similaire: mon 'n' est 1435, 'm' est 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;
}
« d » A la fin est égal au nombre requis.
Êtes-vous faire tuer ici:
for(j=1;j<=i;j++)
t=((long long)t*i)%m;
Exponentials mod m pourraient être mises en œuvre en utilisant la somme de méthode des moindres carrés.
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;
}
Je ne peux pas ajouter un commentaire, mais pour le théorème chinois, voir http: // MathWorld. les formules de wolfram.com/ChineseRemainderTheorem.html (4) - (6).