对于给定的 b
和 N
以及一系列 a
说 (0...n)
,
我需要找到 ans(0...n-1)
哪里,
ans[i]
= a 的
中没有 pow(a, b)modN == i
我在这里搜索的是 pow(a,b)modN
中 a
范围的可能重复,以减少计算时间。
例子:-
如果 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
所以最终的结果是:
ans[0] = 2//我们找到 0 作为答案的次数。
ans[1] = 3
...
最佳答案
您的算法复杂度为 O(n)。 这意味着当 n 变大时需要花费很多时间。
您可以使用复杂度为 O(N) 的算法得到相同的结果。 由于 N << n 它将减少您的计算时间。
首先,两个数学事实:
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
因此,解决您的问题的方法是使用以下循环填充您的结果数组:
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;
}
关于c - 为 a 的范围寻找 pow(a^b)modN,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18041428/