3

与えられたbandとsayNの範囲について、a(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

...

4

2 に答える 2

1

アルゴリズムの複雑さは O(n) です。nが大きくなると時間がかかるということです。

アルゴリズム O(N) でも同じ結果が得られます。N << n なので、計算時間が短縮されます。

まず、2 つの数学的な事実 :

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;
}
于 2013-08-04T11:05:55.017 に答える
0

pow素数のみを計算して、 を使用できますpow(a*b,n) == pow(a,n)*pow(b,n)。

したがって、pow(2,2) mod 3 == 1およびpow(3,2) mod 3 == 2の場合pow(6,2) mod 3 == 2。

于 2013-08-04T10:25:22.087 に答える