Выражение с участием модульных возведения в степень в переполнении стека

Question

Выражение с участием модульных возведения в степень в переполнении стека

Я хочу оценить выражение, (aⁿ + bⁿ + cⁿ) % 1000000003 в C ++. Я получаю ошибки переполнения, когда n очень велико. Может кто-то помочь мне с этим ? Более конкретно a = q + 1, b = - 2 * q а также c = q - 1, Я следовал за функцией, изложенной в этот

Могу ли я сломаться (aⁿ + bⁿ + cⁿ) % 1000000003 в (aⁿ) % 1000000003 + (bⁿ) % 100000003 + (cⁿ) % 1000000003 или что-то подобное?
Также я не могу использовать ничего больше, чем без знака long long int

0

c++exponentiation modular

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вы можете распространять свой модуль. Математически это будет звучать так:

( ((a^n)%1000000003) + ((b^n)%100000003) + ((c^n)%1000000003) ) % 1000000003;

Это избавит вас от необходимости вычисления чисел, выходящих за пределы, что позволит вам выбирать большие значения для n,

доказательство.

Просто обязательно используйте pow в math.h модуль:

( ((pow(a, n))%1000000003)
+ ((pow(b, n))%100000003)
+ ((pow(c, n))%1000000003) ) % 1000000003;

0