2018-09-18

小明在课上学习了进制转化。现在他有q个询问，每次询问想问你在1,门区间内，k进制表示中，k-1的数量最多的数是哪个数。比如当k=2时，9的二进制就是1001，那么他就有2个1。
输入：
测试用例包含多组
第一行一个q，表示有q组询问。
接下来q行，每行三个整数k I, r,分别表示进制数，以及查询的范围。满足1<=q<=100000,2<=k<=16,1<=l<=r<=10^16
输出
对于每组询问，输出答案。如果有多个答案，请输出最小的。
示例：
输入：
1
8 1 100
输出：
63
方法1：
基本思路是将上限转换为k进制，判断第一个是否为k-1，如果是，则k-1次数最多的必然是上限，如果不是，k-1次数最多的这是,本质为等比数列之和。

print("请输入询问次数")
q=int(input())
# q=1
# k=8
# l=1
# r=100
# 方法1
for i in range(q):
    print("请输入k进值")
    k=int(input())
    print("请输入数值的下限")
    l=int(input())
    print("请输入数值范围的上限")
    r=int(input())
    n=1
    while((((k-1)*(1-pow(k,n)))//(1-k))<=r):
        n+=1
    z=(((k-1)*(1-pow(k,n-1)))//(1-k))
    print(z)

方法2：
思路与1类似，但是这个将上限转换为k进制，进行比较，因此方案1比较方便，介绍这个方案，主要是想介绍函数将十进制转换为任意k进制的功能

def f(n,x):
    #n为待转换的十进制数，x为机制，取值为2-16
    b=[]
    lable=True
    while True:
        s=n//x#商
        y=n%x#余数
        if (lable):
            b=[y]
            lable=False
        else:
            b.append(y)
        if s==0:
            break
        n=s
    # b.reverse()
    return b
print("请输入询问次数")
q=int(input())
for i in range(q):
    print("请输入k进值")
    k=int(input())
    print("请输入数值的下限")
    l=int(input())
    print("请输入数值范围的上限")
    r=int(input())
    m=f(r,k)
    z=0
    if (m[len(m)-1]==k-1):
        for j in range(len(m)):
            z+=(k-1)*pow(k,j)
    else:
        for j in range(len(m)-1):
            z+=(k-1)*pow(k,j)
    print(z)