题目

Problem 617. Mirror Power Sequence

新葡京娱乐场:  当前,我国有2亿多进城务工人员在城乡、区域间大规模流动,随之而来的留守儿童问题日益严峻。

For two integers n, e > 1, we define a(n,e)-MPS (Mirror Power Sequence) to be an infinite sequence of integers (ai)i≥0 such that for all i ≥ 0, ai+1 = min(aie, n - aie) and ai > 1.
An example of such sequence is the (18,2)-MPS sequence made of alternating 2 and 4.

Note that even though such a sequence is uniquely determined by n, e and a0, for most values such a sequence does not exist. For example, no (n,e)-MPS exists for n < 6.

Define C(n) to be the number of (n,e)-MPS for some e, and .
You are given that D(10) = 2, D(100) = 21, D(1000) = 69, D(106) = 1303 and D(1012) = 1014800.

Find D(1018).

分析

经过仔细分析,我们发现,对于给定的 e > 1,na0 只能取以下值:

这里的 a > 1,且满足 ae + aN

解答

根据以上分析,我们有以下 C 语言程序:

 1: #include <stdio.h>
 2: #include <math.h>
 3: 
 4: int main(void)
 5: {
 6:   long n = (long)1e18, z = 0;
 7:   for (int e = (int)(log(n-2) / log(2)); e > 1; e--) {
 8:     double e1 = 1.0 / e; long a = (long)pow(n, e1);
 9:     while ((long)pow(a, e) + a > n) a--; z += a - 1;
10:     for (int i = 1; (a = (long)pow(n, e1 /= e) - 1) > 0; i++)
11:       z += a * (i + i + 1);
12:   }
13:   printf("%ld\n", z);
14: }

简要说明:

  • 第 7 行对 e 进行循环。由于需要满足 N - ae ≥ 2,且 a ≥ 2,所以 e 的最大值是 log2 (N - 2)。
  • 第 8 至 9 行利用 ae + aNa 的最大值。
  • 第 9 行的 z += a - 1; 处理的 n = ae + a 情况,之所以减 1,是因为 a ≥ 2。
  • 第 10 至 11 行处理其余情况。第 11 行要乘以 (i + i + 1),是因为 (i + 1)2 - i2 = 2i + 1。

这个程序的运行时间是 0.001 秒。