是否存在常数时间任意进制转换算法？如何优化求最小数位和进制代码

基础疑问 #

是否存在可以在常数时间内将十进制数转换为任意进制数的算法？

具体待解决问题 #

给定三个取值可能非常大的整数a,b,c，满足a>b>c，需要找出取值在[c,b]区间内的某个进制，使得a转换为该进制表示时各位数位之和最小。

举个示例：a = 216, b=7, c=2时输出结果为6：216转二进制是11011000，数位和为4；遍历2到7的所有进制后可以发现，216转6进制结果为1000，数位和为1，是所有取值中最小的。

现有实现问题 #

当前编写的代码运行时出现超时错误，代码如下：

from collections import defaultdict
n = int(input())
for _ in range(n):
    (N,X) = map(int,input().split())
    array = list(map(int,input().split()))
    my_dict = defaultdict(int)

    #original count of elements in array
    for i in range(len(array)):
        my_dict[array[i]] +=1

    #ensure array contains distinct elements
    array = set(array)
    count = max(my_dict.values())  #count= max of single value
    temp = count
    res = None
    XOR_count = float("inf")
    if X==0:
        print(count,0)
        break
    for j in array:
        if j^X in my_dict:
            curr = my_dict[j^X] + my_dict[j]
            if curr>=count:
                count = curr
                XOR_count = min(my_dict[j],XOR_count)
    if count ==temp:
        XOR_count = 0
    print(f"{count} {XOR_count}")

样例输入输出如下：

Sample Input  
3
3 2
1 2 3
5 100
1 2 3 4 5
4 1
2 2 6 6

Sample Output  
2 1
1 0
2 0

待解答的优化问题 #

• 是否有比现有算法更快的任意进制转换实现？
• 有没有其他针对该进制数位和最小问题的优化思路？
• 目前找到了对数换底的相关参考资料，感觉和问题相关但不知道如何应用来解决上述问题。

内容的提问来源于stack exchange，提问作者Patrick_Chong