CSP-J 2020 第一轮 第 22 题：程序（二，k进制计数器进位次数）：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. 错误。当 \(k=1\) 时，对于任意正整数 \(n\)，程序结束时都有 \(\mathrm{len}=2\)。

执行过程如下：

• 初始时，len=1，d[0]=0。
• 第一次外层循环：d[0] 加到 \(1\)，内层循环不执行。最后的 if 成立，将 d[0] 清零、d[1] 设为 \(1\)，并使 len=2。
• 第二次外层循环：d[0] 又加到 \(1\)，内层循环进位，使 d[1] 从 \(1\) 变成 \(2\)。此时最后的判断是 d[1] == 1，不成立，len 不变。
• 此后每次循环，d[1] 都继续增加，不会再等于 \(1\)，所以 len 一直为 \(2\)。

关键是代码判断的是 == k，不是 >= k。

仅取 \(n=1,\ k=1\)，就有 len=2≠n，足以说明原命题错误。