java - 模数运算逻辑以减少计算量

Question

mod的概念只保留余数而不是大数。

计算公式：

=> 求和 i=1 到 i=N { i%m }

约束

1 ≤ N ≤ 10^9 1 ≤ m ≤ 10^9

如何使用模数以便我们不需要求和到 10^9（大数）。Java 代码因超时或 CPU 代码被大量执行错误而终止。

CODE：k是要打印的求和结果。

for (BigInteger bi = BigInteger.valueOf(1);
                bi.compareTo(N) <= 0;
                bi = bi.add(BigInteger.ONE)){

               k = k.add(bi.mod(m));

             }  
        System.out.println(k);

Answer 1

我想我明白你在问什么，在这种情况下，它实际上更像是一个算术而不是一个编程问题，但无论如何它就是这样。尝试一个具体的例子。如果您将 i 的总和从 i % 3 的 1 到 10 加起来，则添加 1 + 2 + 0 + 1 + 2 + 0 + 1 + 2 + 0 + 1。你可以看到你有同样的东西一遍又一遍，所以你需要做的是弄清楚那是什么，弄清楚你需要添加多少次，然后在最后添加剩余的位。