CSP-J 2020 第一轮 第 25 题：程序（二）：n=10^15,k=1时的输出

题目

#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$ 等于：$10^{15}$，输入的 $k$ 为 $1$，则输出等于（  ）。

选项

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

答案

D

题解

答案是 D，\(10^{15}\)。关键是判断条件为 d[j] == k，即恰好等于 1 时才进位。

• 第 1 次外层循环：d[0] 从 0 变成 1。此时 len=1，内层循环不执行。最后的 if 执行，得到：

``text d[0] = 0，d[1] = 1，len = 2，ans = 1 ``

• 第 2 次外层循环：d[0] 加到 1，内层循环在 j=0 时执行进位：

``text d[0] = 0，d[1] = 2，ans = 2 ` 此时最高位 d[1]=2，不等于 1，因此最后的 if 不执行，len` 仍是 2。

• 之后每次循环：d[0] 都从 0 加到 1，再向 d[1] 进位，使 ans 加 1。d[1] 不断增大，再也不会等于 1，所以 len 始终为 2。

因此，每次外层循环恰好使 ans 增加 1，最终： \[ \boxed{\text{ans}=n=10^{15}} \]