CSP-J 2020 第一轮 第 26 题：程序（二）：n=3^30,k=3时的输出

题目

#include <iostream>
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
  cin >> n >> k;
  d[0] = 0;
  len= 1;
  ans = 0;
  for (long long i = 0; i <n; ++i) {
    ++d[0];
    for (int j = 0; j + 1<len; ++j) {
      if (d[j] == k) {
        d[j] = 0;
        d[j + 1] += 1;
        ++ans;
      }
    }
    if (d[len- 1] == k) {
      d[len - 1] = 0;
      d[len] =1;
      ++len;
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}

  假设输入的 $n$ 是不超过 $2^{62}$ 的正整数，$k$ 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：

若输入的 $n$ 等于 $205,891,132,094,649$（即 $3^{30}$），输入的 $k$ 为 $3$，则输出等于（ ）。

选项

• A. $3^{30}$
• B. $(3^{30}-1)/2$
• C. $3^{30}-1$
• D. $(3^{30}+1)/2$

答案

B

题解

答案是 B：\(\dfrac{3^{30}-1}{2}\)。

这段程序实际上是在用数组 d 模拟 三进制加法：

• d[0] 是个位，d[1] 是三位，d[2] 是九位，以此类推。
• 每次外层循环执行 ++d[0]，相当于把这个三进制数加 \(1\)。
• 某一位达到 \(3\)，就清零并向高一位进位，同时 ++ans。

所以，ans 统计的是从 \(0\) 加到 \(n\) 的过程中，所有数位发生进位的总次数。一次加法可能产生多次进位，例如三进制的 \(22+1=100\)，就有两次进位。

当 \(n=3^{30}\) 时：

因此，利用等比数列求和： \[ \text{ans}=3^{29}+3^{28}+\cdots+3+1 =\frac{3^{30}-1}{3-1} =\boxed{\frac{3^{30}-1}{2}}. \]