Страницы

Поиск по вопросам

вторник, 25 декабря 2018 г.

Вычисление (Pow(a,b) mod c) при больших a,b,c

Как вычислить данное выражение не словив переполнение при Pow ?
ulong Pow(ulong a, ulong b) { ulong p = 1; for (ulong i = 0; i < b; ++i) p *= a; return p; }
ulong m = Pow(a, b) % c;


Ответ

Если a * c не вылезает за ulong, то так:
ulong Pow(ulong a, ulong b) { a = a % c; ulong p = 1; for (ulong i = 0; i < b; ++i) p = (p * a) % c; return p; }
Инвариант: p < c. При умножении p * a < c * a, и по условию переполнения не происходит.

Обновление: для больших значений степени имеет смысл умножать путём последовательного возведения в квадрат.
ulong Pow(ulong a, ulong b) { a = a % c; ulong p = 1; ulong r = 1; while (b > 0) { if (b % 2 != 0) r = (r * p) % c; b = b / 2; p = (p * a) % c; } return r; }

Комментариев нет:

Отправить комментарий