找到POW（一个^ B）MODN为一系列一的 [英] Finding pow(a^b)modN for a range of a's

问题描述

对于给定的 B 和 N 和一系列 A 说（0，...，N），

For a given b and N and a range of a say (0...n),

我需要找到答（0，...，N-1） 在这里，

答[我] =无的 A的为其 POW（A，B ）MODN ==我

我正在寻找在这里是 A可能重复POW（A，B）MODN 为一系列 A ，以减少计算时间。

What I am searching here is a possible repetition in pow(a,b)modN for a range of a, to reduce computation time.

例： -

如果 B = 2 N = 3 和 N = 5

for a in (0...4):
    A[pow(a,b)modN]++;

所以这将是

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

所以最终的结果将是：

so the final results would be:

答[0] = 2 //没有的时候，我们已经找到0作为答案。

答[1] = 3

...

推荐答案

您的算法有一个为O（n）的复杂性。 这意味着它需要大量的时间，当n变大。

Your algorithm have a complexity of O(n). Meaning it take a lot of time when n gets bigger.

您可以有相同的结果与算法O（N）。 随着N＆LT;＆LT; ñ它会降低你的计算时间。

You could have the same result with an algorithm O(N). As N << n it will reduce your computation time.

Firts，两人的数学事实：

Firts, two math facts :

pow(a,b) modulo N == pow (a modulo N,b) modulo N

和

if (i < n modulo N)
   ans[i] = (n div N) + 1
else if (i < N)
   ans[i] = (n div N)
else
   ans[i] = 0

因此​​，一个解决问题的方法是，以填补下面的循环你的结果数组：

So a solution to your problem is to fill your result array with the following loop :

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

这篇关于找到POW（一个^ B）MODN为一系列一的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！