Я хочу оценить выражение, (a n + b n + c n) % 1000000003
, в C++. Я получаю ошибки переполнения, когда n очень велико. Может кто-то помочь мне с этим? Более конкретно a = q + 1, b = - 2 * q
и c = q - 1
. Я выполнял функцию, изложенную в этом
Могу ли я сломать (a n + b n + c n) % 1000000003
в (a n) % 1000000003 + (b n) % 100000003 + (c n) % 1000000003
или что-то подобное? Также я не могу использовать ничего больше, чем unsigned long long int
Вы можете распространять свой модуль. Математически это будет звучать:
( ((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;