CSP-J 2020 第一轮 第 23 题：程序（二）：k 1时len是否一定小于n

题目

#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$ 的正整数，完成下面的判断题和单选题：

若 $k>1$，则输出 $\mathrm{ans}$ 时，$\mathrm{len}$ —定小于 $n$。（  ）

选项

• A. 正确
• B. 错误

答案

B

题解

选 B. 错误。题目说“一定小于”，只要找到一个反例即可。

取 \(n=2,\ k=2\)：

• 初始时，len = 1，d[0] = 0。
• 第一次循环后，d[0] = 1，没有进位，len = 1。
• 第二次循环中，d[0] 变成 \(2\)，满足最后一个 if 的条件，于是 d[0] = 0、d[1] = 1，并执行 ++len，使 len = 2。

输出时 \(\mathrm{len}=n=2\)，不满足 \(\mathrm{len}<n\)，所以判断错误。