如何正确使用Mod10^9+7

Question

在 Java 中，我需要计算前 n 个数字的平方和，即

1^2 + 2^2+ 3^2+.....+n^2

也就是

n(n+1)(2n+1)/6

或

n^3/3 + n^2/2 + n/6

然后我需要计算另一个值

n*(n-1/2)^2

因为 n 会很大，答案可以是 "answer%M"，其中 M 是 10^9+7。

我无法理解应该在哪个计算点执行操作 %M。例如

n%M * (n+1)%M (2n+1)%M /  6

或

(n(n+1)(2n+1)/6)%M

你能帮帮我吗？一般来说，请提供使用 %M; 的指南，以便我下次可以决定。

Answer 1

/运算符不能取模：(a/b) % M != ((a % M)/(b % M)) % M，所以只需要最后取模：

(n*(n+1)*(2n+1)/6) % M

有关详细信息，请阅读 Modulo operation。并且不要忘记使用 BigInteger class 来计算非常大的数字。

Answer 2

(n(n+1)(2n+1)/6)%M理论上是正确的，n%M * (n+1)%M * (2n+1)%M / 6是不正确的。

如果n很大，(n(n+1)(2n+1)/6)的中间计算会溢出你的整数类型，所以第一种方法也不尽如人意

计算a*b/c % M的一般解决方案是计算cmodM的modular inverse（比如c'）和然后计算：((a%M * b%M)%M * c')%M

在这里，它更简单一些，因为您除以一个常数 (6)，并且可以在三项中找到并剔除 2 和 3 的因数。像这样的伪代码：

n1 := n
n2 := n+1
n3 := 2n+1
if n1 % 2 == 0 { n1 /= 2 } else { n2 /= 2 }
if n1 % 3 == 0 { n1 /= 3 } else if n2 % 3 == 0 { n2 /= 3 } else { n3 /= 3}
return (((n1 % M) * (n2 % M)) % M * (n3 % M)) % M

如何正确使用Mod10^9+7

How to correctly use Mod 10^9+7

java

algorithm

largenumber

modulo