Finding пау (а^Ь) MODn для ряда элементов а

Для данного b и N и ряд a говорят (0...n),Finding пау (а^Ь) MODn для ряда элементов а

Мне нужно, чтобы найти ans(0...n-1) где,

ans[i] = ЧИСЛО a's, для которых pow(a, b)modN == i

То, что я ищу здесь это возможно повторение в pow(a,b)modN для диапазона a, чтобы уменьшить время вычислений.

Пример: -

если b = 2N = 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

...

источник

2013-08-04 Ninja420

Какие кодирования оспаривать эту проблему? –

Просьба привести пример, чтобы мы поняли проблему. –

@UchiaItachi обновлено .. – Ninja420

Ваш алгоритм имеет сложность O (n). Значит, это занимает много времени, когда n становится больше.

Вы можете получить тот же результат с помощью алгоритма O (N). As 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; 
}

источник

2013-08-04 11:05:55

Спасибо тонну! : D – Ninja420

'' Ваш алгоритм имеет сложность O (n) "' - Я не уверен, что я считаю, что 'a^b' является операцией' O (1) '. – Dukeling

Вы правы. Но это зависит от вашей процессорной архитектуры. На x86 предполагается, что это пример времени.Nevermind, я должен признать, что, возможно, я упростил вычисление своих вычислений, не принимая во внимание это, так как это влияет на оба алгоритма одинаково. Спасибо за замечания. –

Вы можете рассчитать 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-04 10:25:22 ugoren

Finding пау (а^Ь) MODn для ряда элементов а

ответ

Смежные вопросы