CSP-J 2020 第一轮 第 24 题：程序（二）：k 1时k^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}$ 时，$k^{len}$ —定大于 $n$。（  ）

选项

• A. 正确
• B. 错误

答案

A

题解

选 A. 正确。

当 \(k>1\) 时，数组 d 实际上在模拟一个 \(k\) 进制数，d[0] 是最低位，len 是位数。

每次外层循环都会：

• 执行 ++d[0]，相当于这个数加 \(1\)；
• 某一位达到 \(k\) 时，将它清零，向高位进 \(1\)；
• 如果最高位也需要进位，就新增一位，并令 len 加 \(1\)。

初始表示的数是 \(0\)，经过 \(n\) 次加一后，数组表示的就是 \(n\)。

因此，\(n\) 是一个 len 位的 \(k\) 进制正整数，满足 \[ k^{len-1}\le n<k^{len}. \] 所以 \(k^{len}\) 一定大于 \(n\)。

特别地，若 \(n=k^m\)，它的 \(k\) 进制表示为 \(1\) 后面跟 \(m\) 个 \(0\)，此时 len 为 \(m+1\)，仍然满足严格大于。