c++ - C++ 中涉及模幂的表达式

Question

我想在 C++ 中评估表达式 , 。当 n 非常大时，我会出现溢出错误。有人可以帮我弄这个吗 ？更具体地说，和。我一直在关注本文中概述的功能(an + bn + cn) % 1000000003a = q + 1, b = - 2 * qc = q - 1

我可以闯入或类似的东西吗？我也只能使用unsigned long long int(an + bn + cn) % 1000000003(an) % 1000000003 + (bn) % 100000003 + (cn) % 1000000003

Answer 1

您可以分发您的模数。从数学上讲，这将是合理的：

( ((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;