CSP-J 入门级 · CSP 2020 入门级第一轮 第 17 题

2.

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

• 判断题

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

• 单选题

4) 若输入的 $n$ 等于：$10^{15}$，输入的 $k$ 为 $1$，则输出等于（ ）。

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

6) 若输入的 $n$ 等于 $100,01

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

模拟k进制加法器。d[]存储k进制数的每一位，每次+1，记录进位次数ans。本质是计算从0到n-1在k进制下所有进位次数之和。

核心理解：程序模拟从0开始每次+1，累加到n次（共n个1）。ans记录进位发生次数。len记录当前k进制数的长度。

考察知识点：模拟 + 进制转换 + 数论

程序功能分析： 1. d[]存储以k进制表示的数字，d[0]为最低位 2. 每次循环给该数加1（++d[0]） 3. 如果某位达到k，则进位（归0，高位+1） 4. ans记录所有进位次数

规律： 每次从0加到n-1，进位次数相当于n在k进制下所有非最低位数字之和。 因为：每当某位从k-1变成0（即产生进位时）ans++。

逐题解析： 1. ❌ k=1时，所有位都是0，每次+1都产生进位。这实际上是二进制表达式，len会增长但未必等于n。 2. ❌ k>1时，len不一定小于n。例如n很大时len可能接近log_k(n)。 3. ✅ k^len一定大于n（因为len是n的k进制表示的长度，k^(len-1)≤n<k^len） 4. n=10^15, k=1→退化为每次加1都进位→ans=n=10^15 5. n=3^30, k=3→3进制下3^30=1后面30个0→每位的数字之和...实际进位次数=(3^30-1)/2 6. n=100,010,002,000,090, k=10→计算这个数在10进制下的前缀和等