Как вычислить данное выражение не словив переполнение при 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;
}
Комментариев нет:
Отправить комментарий