Pour un b et N donnés et une plage de parole (0...n) ,
J’ai besoin de trouver ans(0...n-1) où,
ans[i] = nombre de a's pour lesquels pow(a, b)modN == i
Ce que je recherche ici est une possibilité de répétition dans pow(a,b)modN pour une plage de a , afin de réduire le temps de calcul.
Exemple:-
si b = 2 N = 3 et n = 5
for a in (0...4): A[pow(a,b)modN]++;
donc ce serait
pow(0,2)mod3 = 0 pow(1,2)mod3 = 1 pow(2,2)mod3 = 1 pow(3,2)mod3 = 0 pow(4,2)mod3 = 1
donc les résultats finaux seraient:
ans[0] = 2 // no of times we have found 0 as answer .
ans[1] = 3
...
Votre algorithme a une complexité de O (n). Cela signifie que cela prend beaucoup de temps lorsque n devient plus grand.
Vous pourriez avoir le même résultat avec un algorithme O (N). Comme N << n, votre temps de calcul sera réduit.
Premièrement, deux faits mathématiques:
pow(a,b) modulo N == pow (a modulo N,b) modulo N
et
if (i < n modulo N) ans[i] = (n div N) + 1 else if (i < N) ans[i] = (n div N) else ans[i] = 0
Une solution à votre problème consiste donc à remplir votre tableau de résultats avec la boucle suivante:
int nModN = n % N; int nDivN = n / N; for (int i = 0; i < N; i++) { if (i < nModN) ans[pow(i,b) % N] += nDivN + 1; else ans[pow(i,b) % N] += nDivN; }
Vous pouvez calculer pow pour les nombres premiers uniquement et utiliser pow(a*b,n) == pow(a,n)*pow(b,n) .
Donc si pow(2,2) mod 3 == 1 et pow(3,2) mod 3 == 2 , alors pow(6,2) mod 3 == 2 .