CSP-J 2020 第一轮 第 27 题：程序（二）：n=100,010,002,000,090,k=10时的输出

题目

#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$ 等于 $100,010,002,000,090$，输入的 $k$ 为 $10$，则输出等于（ ）。

选项

• A. $11,112,222,444,543$
• B. $11,122,222,444,453$
• C. $11,122,222,444,543$
• D. $11,112,222,444,453$

答案

D

题解

答案是 D：\(11,112,222,444,453\)。

这段程序模拟的是：从 \(0\) 开始，每次加 \(1\)，一直加到 \(n\)，统计总共发生了多少次进位。

当 \(k=10\) 时，数组 d 存储十进制的各位数字，d[0] 是个位。每当某一位达到 \(10\)，就把这一位清零、向高一位进 \(1\)，同时 ans 加 \(1\)。

可以通过“各位数字之和”快速计算：

• 每执行一次 ++d[0]，数字之和增加 \(1\)，共增加 \(n\)。
• 每发生一次进位，当前位从 \(10\) 变成 \(0\)，高一位增加 \(1\)，所以数字之和减少 \(9\)。

因此，最终有 \[ n-9\,ans=\text{\(n\) 的各位数字之和}. \]

对于 \(n=100,010,002,000,090\)，各位数字之和为 \[ 1+1+2+9=13. \]

所以 \[ ans=\frac{n-13}{9} =\frac{100,010,002,000,077}{9} =\boxed{11,112,222,444,453}. \]