Bittttttts

用java写的，最后还是通过了 但速度有点慢。这都不是关键，具体讲解一下思路。
首先将start（我用start和end分别表示左右的边界）转换成k进制。将转换后的每一位都存在arraylist中（数组和linklist也可以，自己选）。然后从低位往高位依次将每一位变成（k-1）。在变换之前，首先看看能不能变，能变则变，不能变表示超过了end，这个时候直接跳出即可。

import java.util.ArrayList;
import java.util.Scanner;
public class Main {

    public static long minNum(int k, long start, long end) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        long tmp = start;
        while (tmp != 0) {
            long rest = tmp % k;
            list.add((int) rest);
            tmp = tmp / k;
        }
        long sum = 1;
        for (int i = 0; i < list.size(); i++) {
            long num = list.get(i);
            num = k - 1 - num;
            long size = (long) (num * sum);
            if (start + size <= end) {
                start = start + size;
            } else {
                return start;
            }
            sum = sum * k;
        }
        while (start < end) {
            long size = (long) ((k - 1) * sum);
            if (start + size <= end) {
                start = start + size;
            } else {
                return start;
            }
            sum = sum * k;
        }
        return start;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int time = in.nextInt();
            for (int i = 0; i < time; i++) {
                int k = in.nextInt();
                long start = in.nextLong();
                long end = in.nextLong();
                System.out.println(minNum(k, start, end));
            }
        }
    }
}

q = int(input().strip())

# 将十进制转换为k进制，k进制的每一位，用列表中的一个数表示，注意当k 大于10时，k 进制中的每一位可能为两位数
def dec2k(dec):
    ansk = []
    while dec // k:
        ansk.append(dec % k)
        dec = dec // k
    ansk.append(dec)
    ansk = ansk[::-1]
    return ansk

# 将k进制转换为十进制，k进制的每一位，用列表中的一个数表示，注意当k 大于10时，k 进制中的每一位可能为两位数
def k2dec(rans):
    ansd = 0
    tmp = 1
    for i in range(len(rans)-1, -1, -1):
        ansd += rans[i] * tmp
        tmp *= k
    return ansd
# k进制表示中，k-1的数量最多的数，且输出最小的，即k进制数每一位均为k-1构成
def get_ans():
    if len(lvalue) == 0 or len(rvalue) == 0:
        return
    # 第一种全为(k-1), l <= and <= r
    record, tmp = 0, 0
    while tmp <= r:
        record = tmp
        tmp = tmp * k + (k-1)
    # print("record:", record)
    if record >= l:
        return record

    else:
        ''' # 每判断一下都需要进制转换，复杂度太高，超时，由于每次只更新一位，因此，可以直接修改
        for i in range(len(lvalue)-1, -1, -1):
            t = lvalue[i]
            lvalue[i] = k-1
            if k2dec(lvalue) > r:  # 大于，则还原
                lvalue[i] = t
                return k2dec(lvalue)
        '''

        dec = k2dec(lvalue)
        tmp = 1
        for i in range(len(lvalue) - 1, -1, -1):
            dec = dec + (k - 1 - lvalue[i]) * tmp
            tmp = tmp * k
            t = lvalue[i]
            lvalue[i] = k - 1
            if dec > r:  # 大于，则还原
                lvalue[i] = t
                return k2dec(lvalue)

while q > 0:
    k, l, r = map(int, input().strip().split())
    lvalue = dec2k(l) 
    rvalue = dec2k(r) 
    print(get_ans())
    q -= 1

'''
15
4 8442097414683844 8442097414683844
3 3173466882309064 3173466882309073
4 8527527027194177 8527527027194276
4 2661113491247500 2661113491248499
16 4448712248766526 4448712248776525
13 2684426398058983 2684426398158982
14 6562761408288807 6562761409288806
4 2847109288743406 2847109298743405
12 3011167199031338 3011167299031337
7 8655416323525458 8655417323525457
13 177186968879953 177196968879952
2 4133390730537405 4133490730537404
13 4680075382111731 4681075382111730
11 5341708995347620 5351708995347619
8 114951857079067 214951857079066
'''

 您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为86.67%

在本地跑，测试用例都通过了，不知道是哪里出现问题，我已经将原有的进制转换优化了，复杂度应该是O(n),难道真的是Python运行太慢了？？？有大佬麻烦指点一下，谢谢

import java.util.ArrayList;
import java.util.Scanner;
/*
 *    低位变 k-1 时，巧妙做法：假如百位数是5（八进制），
 *    那么变成七（八进制数百位）要加 2，对应十进制数要加 2*(8^2)
 */
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			int k = sc.nextInt();
			long l = sc.nextLong();
			long r = sc.nextLong();
			System.out.println(count(k, l, r));
		}
	}

	public static long count(int k, long l, long r) {
//		int num = 0;
//		String str_l = invert(l, k);
//		String str_r = invert(r, k);
		
		ArrayList<Long> start = invert(l,k);
		long sum = 1;
		for(int i = 0;i < start.size();i++){
			long ii = k - 1 - start.get(i);
			if(l + ii * sum <= r){
				l = l + ii * sum;
			}else{
				return l;
			}
			sum *= k;
		}
		
		// 当l所有k进制数位全变成k-1时，仍不超过r时
		while(l < r){
//			long iii = k * sum;
			long iii = (k - 1) * sum;
			if(l + iii <= r){
				l += iii;
			}else{
				return l;
			}
			sum *=k;
		}
		// for(int i = 0;i < )
		return l;
	}

	// public static String invert(long x,int k){
	// LinkedList<Long> ll = new LinkedList<>();
	// long r = 0;
	// while(x > 0){
	// r = x % k;
	// ll.addFirst(r);
	// x /= k;
	// }
	// StringBuffer sb = new StringBuffer();
	// for(int i = 0;i < ll.size();i++){
	// sb.append(ll.get(i));
	// }
	// return sb.toString();
	// }
	public static ArrayList<Long> invert(long x, int k) {
		ArrayList<Long> arr = new ArrayList<>();
		long r = 0;
		while(x > 0){
			r = x % k;
			arr.add(r);
			x /= k;
		}
		return arr;
	}
}

q = int(input())
from collections import deque
from math import pow
def ToK(num,k):
    res = deque()
    while num:
        res.appendleft(num%k)
        num //= k
    return list(res)
def Tonum(res,k):
    ans = 0
    temp = 1
    for i in range(len(res)-1,-1,-1):
        ans += res[i] *temp
        temp *= k
    return ans
    #ans = 0
    #temp = 0
    #for i in reversed(range(len(res))):
    #    ans += res[i] * pow(k,temp)
    #    temp += 1
    #return int(ans)


for i in range(q):
    k, l, r = tuple(map(int, input().split()))
    record, tmp = 0, 0
    while tmp <= r:
        record = tmp
        tmp = tmp * k + (k - 1)
    if record >= l:
        print(record)
    else:
        low_k = ToK(l,k)
        for i in reversed(range(len(low_k))):
            if low_k[i] == k-1:
                continue
            else:
                change = low_k[i]
                low_k[i] = k-1
                if Tonum(low_k[:],k) > r:
                    low_k[i] = change
                    break
        print(Tonum(low_k[:],k))

import math
q = int(input())

def func(k, l, r):
    if l == r: return l
    if l == 0: return l
    order = math.ceil(math.log(l, k))

    flag =False # k=10为例：寻找 [l,r] 内是否有 99，999，9999... 如果有，就输出最长的 9999。
    for i in range(order, math.ceil(math.log(r, k)) + 1):
        mid = k ** i - 1
        if mid <= r and mid >= l:
            min_res = mid
            flag = True
    if flag:
        return min_res

    
    # 上一部如果没找到连续的 9 组成的数，那就不看最高位，只看后面几位，如此递归下去：
    # k=10: 【3333，5678】-> 3000 +【333，2678】-> 3000 + 999 = 3999
    else: 
        left_ = k ** (order - 1)
        left = left_ * int(l / left_)
        min_res = left + func(k, l - left, r - left)

    return int(min_res)


for i in range(q):
    k, l, r = [int(x) for x in input().split()]
    print(func(k, l, r))

不需要很复杂吧，还差一步递归最后终止的判断，否则特殊情况死循环

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> rdec2k(long long dec, int k) {
    vector<int> ans;
    while (dec / k) {
        ans.push_back(dec % k);
        dec = dec / k;
    }
    ans.push_back(dec);
    return ans;
}
void get_ans(vector<int> &vrans, vector<int> &vrl, vector<int> &vrr, int k) {
    if (vrl.empty() || vrr.empty()) {
        return;
    }
    if (vrl.size() < vrr.size()) {
        vrans.assign(vrr.size() - 1, k - 1);
    }
    else { // vrl.size() < vrr.size()
        if (vrr.back() > vrl.back()) {
            vrans.assign(vrl.size() - 1, k - 1);
            vrans.push_back(vrl.back());
            //return;
        }
        else {// vrr.back() == vrl.back()
            int tmp = vrl.back();
            vrl.pop_back();
            vrr.pop_back();
            get_ans(vrans, vrl, vrr, k);
            vrans.push_back(tmp);
        }
    }
}
long long k2dec(vector<int> vrans, int k) {
    long long ans = 0;
    long long tmp = 1;
    for (int i = 0; i < vrans.size(); ++i) {
        ans += vrans[i] * tmp;
        tmp *= k;
    }
    return ans;
}
int main() {
    int N;
    while (cin >> N) {
        while (N--) {
            int k;
            long long l, r;
            cin >> k >> l >> r;
            vector<int> vrl = rdec2k(l, k); // 逆序存放k进制的l
            vector<int> vrr = rdec2k(r + 1, k); // 逆序存放k进制的r+1, 数可以取的范围是[l, r+1)
            vector<int> vrans; // 逆序存放k进制的答案
            get_ans(vrans, vrl, vrr, k);
            cout << k2dec(vrans, k) << endl; // 将答案转化成10进制后输出
        }
    }
    return 0;
}

以上是代码