Recherche de pow (a ^ b) modN pour une plage de a

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 .