解题思路

• 观察：每次把一个 1 加到序列末尾；若有 k 个相邻且相等为 x，就合并为一个 x+1。这个过程与“k 进制加一并进位”完全一致： 将序列中“值为 x 的元素个数”记为 cnt[x]，始终有

  $$\sum_{x\ge1} cnt[x]\cdot k^{x-1}=n$$

  （一次合并把 k 个 x 变成一个 x+1，两边权重都等于 k\cdot k^{x-1}=k^x）。

• 终止态性质：若还存在 k 个相邻的 x 就能继续合并，所以终止时对所有 x 都有 0\le cnt[x]<k。而且序列在整个过程中保持非增（左大右小），因此最终形态一定是从大到小的“分块”：L、L-1、…、1，每个值各出现 cnt[x] 次。

• 于是 cnt[x] 正是 n 的 k 进制展开 的各位数字： 令 n = a_0 + a_1 k + a_2 k^2 + ...，其中 0 ≤ a_i < k，则 cnt[i+1]=a_i。 最终答案就是把数值从大到小输出：对 i 从最高位到 0，输出 (i+1) 这个十进制串，重复 a_i 次并拼接。

• 算法要点：

  1. 先把 n 转为 k 进制得到各位 a_i = n % k；
  2. 从高位到低位依次把字符串 str(i+1) 复制 a_i 次拼到答案上。 这避免了实际模拟，正确且高效。

复杂度分析

• 时间复杂度：将 n 转为 k 进制需要 O(log_k n)，输出本身的长度记为 AnsLen，总体 O(log_k n + AnsLen)。
• 空间复杂度：存放各位数字，需要 O(log_k n)。

代码实现

Python

# 题面功能放在函数里，主函数只负责读写
import sys

def build_answer(n: int, k: int) -> str:
    # 将 n 转为 k 进制，得到各位 a_i（低位在前）
    digits = []
    while n > 0:
        digits.append(n % k)
        n //= k
    # 从高位到低位输出 (i+1) ，重复 a_i 次
    res_parts = []
    for i in range(len(digits) - 1, -1, -1):
        cnt = digits[i]
        if cnt == 0:
            continue
        val_str = str(i + 1)  # 当前块的值
        res_parts.append(val_str * int(cnt))
    return "".join(res_parts)

def main():
    data = sys.stdin.read().strip().replace('\n', ' ').split()
    n = int(data[0])
    k = int(data[1])
    print(build_answer(n, k))

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main（ACM 风格）
import java.io.*;
import java.util.*;

public class Main {
    // 功能函数：根据 n、k 构造答案
    static String buildAnswer(long n, int k) {
        // 保存 k 进制各位（低位在前）
        ArrayList<Integer> digits = new ArrayList<>();
        while (n > 0) {
            digits.add((int)(n % k));
            n /= k;
        }
        StringBuilder sb = new StringBuilder();
        // 从高位到低位输出 (i+1)，重复 a_i 次
        for (int i = digits.size() - 1; i >= 0; --i) {
            int cnt = digits.get(i);
            if (cnt == 0) continue;
            String val = Integer.toString(i + 1);
            for (int t = 0; t < cnt; ++t) sb.append(val);
        }
        return sb.toString();
    }

    public static void main(String[] args) throws Exception {
        // 数据范围不大，使用常规输入即可
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] parts = line.trim().split("\\s+");
        long n = Long.parseLong(parts[0]);
        int k = Integer.parseInt(parts[1]);
        System.out.print(buildAnswer(n, k));
    }
}

C++

// ACM 风格，读入后调用外部函数完成计算
#include <bits/stdc++.h>
using namespace std;

// 功能函数：根据 n、k 构造答案字符串
string buildAnswer(unsigned long long n, unsigned long long k) {
    vector<unsigned int> digits; // k 进制各位（低位在前）
    while (n > 0) {
        digits.push_back((unsigned int)(n % k));
        n /= k;
    }
    string res;
    // 从高位到低位输出 (i+1)，重复 a_i 次
    for (int i = (int)digits.size() - 1; i >= 0; --i) {
        unsigned int cnt = digits[i];
        if (cnt == 0) continue;
        string val = to_string(i + 1); // 当前块的值
        for (unsigned int t = 0; t < cnt; ++t) res += val;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unsigned long long n, k;
    if (!(cin >> n >> k)) return 0;
    cout << buildAnswer(n, k);
    return 0;
}

题目内容

首先，你有一个为空的序列，接下来会进行 $n$ 次操作：

每次操作：将一个单独的数字 $1$ 放入序列末尾；

如果序列中出现 $k$ 个相邻的元素都等于 $x$ ，则这 $k$ 个元素会合并成一个元素，值为 $x+1$ ；

合并后可能会触发新的合并操作，直到序列中不存在可合并区间为止。

定义最终序列中的元素依次拼接成一个十进制数，作为答案输出。

输入描述

在一行上输入两个整数 $n,k(1≦n≦10^{18};2≦k≦2×10^5)$ ，分别表示操作总次数，合并阈值。

输出描述

在一行上输出一个整数，表示最终序列中所有元素从左到右拼接形成的十进制数。

样例1

输入

5 2

输出

3 1

说明

在这个样例中，操作如下：

• 第一次，序列由 { } 变为 { $1$ }；

• 第二次，序列由 {$1$} 变为 {$1,1$}，随后两个相邻的 $1$ 合并成 {$2$}；

• 第三次，序列由 {$2$} 变为 {$2,1$};

• 第四次，序列由 {$2,1$} 变为 {$2,1,1$}，先合并 {$1,1$}→$2$ 得 {$2,2$}，再合并 $2,2→3$ 得 {$3$ };

• 第五次：序列由 {$3$} 变为 {$3,1$}。