对于一个给定的b
andN
和一个范围a
say (0...n)
,
我需要找到ans(0...n-1)
在哪里,
ans[i]
=a's
没有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 // no of times we have found 0 as answer .
ans[1] = 3
...