在C++中涉及模冪的表達式

Question

我想要在C++中評估表達式(an + bn + cn) % 1000000003。當n非常大時，我會出現溢出錯誤。有人可以幫我弄這個嗎 ？更具體地說a = q + 1, b = - 2 * q和c = q - 1。我一直在遵循this

中概述的功能我可以將(an + bn + cn) % 1000000003分爲(an) % 1000000003 + (bn) % 100000003 + (cn) % 1000000003或類似的東西嗎？ 我也不能使用任何超過無符號長long int類型

Answer 1

您可以發佈模。在數學上，這將是聲音：

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

這將阻止您不必計算界限以外的數字，讓您獲得n選擇較大的值。

Proof。

只是要確保math.h模塊中使用pow：

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