计算一大笔的模数

Question

我需要计算

 1^2 + 2^2 + ... + n^2 modulo 10234573 

对于n高达20亿元.我需要使用本机C++库.我无法弄清楚如何做到这一点,因为它看起来像是一个巨大的数字.

Answer 1

您可以通过轻松的证明归纳说

 1 + 4 + 9 + 16 + ... + k**2 + ... + n**2 == n * (n + 1) * (2 * n + 1) / 6

http://oeis.org/A000330

唯一的困难是你必须除以6,因为总和是一个整数值,你必须考虑6案例(每个可能的n mod 6结果):

int SumOfSquares(int n) {
  int64_t modulo = 10234573;

  int64_t a = n;
  int64_t b = a + 1;     /* even n+1 can exceed the limit; let's change n to a */
  int64_t c = 2 * a + 1; /* 2*n can exceed the limit; let's change n to a */

  switch (n % 6) {
    case 0:
      a /= 6;
      break;
    case 1:
      b /= 2;
      c /= 3;
      break;
    case 2:
      a /= 2;
      b /= 3;
      break;
    case 3:
      a /= 3;
      b /= 2;
      break;
    case 4:
      a /= 2;
      c /= 3;
      break;
    case 5:
      b /= 6;
      break;
  }

  /* combersome to ensure we are in [0..modulo ** 2] range */
  return (int) (((((a % modulo) * (b % modulo)) % modulo) * (c % modulo)) % modulo);
}  

我们可能会有一个因素(modulo - 1) ** 2 == 104746484492329,因为这超过了最大可能的32位整数值(2147483647),我们必须使用int64_t这些因子.

int result = SumOfSquares(2000000000); /* result == 986488 */