题目

不超过 999 的正整数中,3 或 5 的倍数的和是多少?

用穷举法暴力解答

最简单的做法就是从 1 开始,依次枚举,累加 3 或 5 的倍数,直到 999 为止。

使用组合数学公式解答

根据组合数学的容斥原理,这道题的答案是:

根据等差数列的求和公式,我们有:

测试程序

我们使用规模更大的问题来测试:

不超过 999,999,999 的正整数中,7、9、10、11 或 13 的倍数的和是多少?

我们有以下 C 程序:

#include <stdio.h>
#include <time.h>

long c1(long n, int a[], int size)
{
  long z = 0;
  for (long i = 1; i <= n; i++) {
    int b = 0;
    for (int j = 0; j < size; j++)
      if (i % a[j] == 0) { b = 1; break; }
    if (b) z += i;
  }
  return z;
}

long f(long n, long d) { return n /= d, (d * n * (n + 1)) >> 1; }

long c2a(long n, int a[], int size, long m, int odd)
{
  long z = 0;
  for (int i = size - 1; i >= 0; i--) {
    long d = m * a[i];
    // printf("%cf(%ld) ", odd ? '-' : '+', d);
    z += (odd ? (-1) : 1) * f(n, d) + c2a(n, a, i, d, !odd);
  }
  return z;
}

long c2(long n, int a[], int size) { return c2a(n, a, size, 1, 0); }

void test(const char* msg, long (*c)(long, int[], int),
  long n, int a[], int size)
{
  clock_t t = clock();
  long z = c(n, a, size);
  t = clock() - t;
  printf("%s: %ld, %9lf seconds\n", msg, z, (double)t/CLOCKS_PER_SEC);
}

int main(void)
{
  static int a[] = {7, 9, 10, 11, 13};
  long n = 999999999;
  int size = sizeof(a) / sizeof(a[0]);
  test("c1", c1, n, a, size);
  test("c2", c2, n, a, size);
  return 0;
}

上述程序中,数组 a 中的数必须两两互素。如果不是这样,就要把 c2a 函数中的

long d = m * a[i];

改为(其中 lcm 函数用于求最小公倍数):

long d = lcm(m, a[i]);

简要说明:

  • 函数 c1 使用穷举法暴力解答。
  • 函数 c2 使用容斥原理解答。
    • 函数 f 利用等差数列的求和公式来计算。
    • 函数 c2a 通过递归调用自身来实施容斥原理。

编译和运行

$ clang -O 001-ext.c && ./a.out
c1: 212287710212288799, 49.706292 seconds
c2: 212287710212288799,   0.000002 seconds

分析

如果把 main 函数中的

static int a[] = {7, 9, 10, 11, 13};

改为

static int a[] = {2, 3, 5, 7};

并且删除 c2a 函数中的 printf 语句前面的//,则可以得到:

+f(7) -f(35) +f(105) -f(210) +f(70) -f(21) +f(42) -f(14) +f(5) -f(15) +f(30) -f(10) +f(3) -f(6) +f(2)

由此可以窥视这个程序是如何实施容斥原理的:

参考资料

  1. Wikipedia: Inclusion–exclusion principle
  2. 图灵社区:欧拉计划:001. 3和5的倍数