algorithm - 计算线性序列模 n 的总和

Question

我希望有效地计算以下总和:

sum (i=0..max) (i * A mod B)

可以假设 max，A < B 并且 A 和 B 互质(否则可以很容易地归约)。数字很​​大，所以简单的迭代效率太低了。 到目前为止，我还没有想出多项式时间算法(即 log(B) 中的多项式)，我能找到的最好的是 O(sqrt(max))。这是一个已知的难题，还是有人知道多项式时间算法？

需要明确的是，“mod B”仅适用于 i*A，不适用于总和。所以例如

总和(i=0..3) (i*7 mod 11) = 0 + 7 + 3 + 10 = 20。

Answer 1

你可以稍微改变一下以获得

 A*(sum(i=0..max)) mod B

简化为

 A*(max*(max+1)/2) mod B

现在您只需要执行一次(可能是大整数)乘法(假设 max 本身不是太大)，然后进行一次(大整数)模运算。