版权声明:本文为博主原创文章未经博主允许不得转载。 /m0_/article/details/
:题意 给出两个数字n1n2,tag和进制r如果tag=1,说明n1是r进制数求n2在几进制的情况下与n1相等。如果tag=2说明n2是r进制数,求n1在几进制的情况下与n2相等
:思路 题解一般用的是二分查找法,水水说如果这样做他很难确定上界是多少然后就用的特判来避免的超時。
首先这两个数字都是以字符形式输入的,len1表示未知进制数的长度len2表示已给出进制数的长度。将各个位上的字符转化为数字
- 比较未知进制数的各个位上数字并求出最大值st,也就是查询几进制能满足相等条件 这个进制的下界
- 将已知r进制数转为10进制数ans,用于比较
- 将進制从st开始跑,将 i 进制数转十进制的结果ans1 并与ans进行比较如果相等就输出 i 进制,如果大于输出 Impossible
但是这样做会超时,可以想一下如果已知進制的数字转为十进制是未知是100,那么循环跑的最大进制是100000时间复杂度是根号n,如果未知是10那么循环的最大进制是,时间复杂度是n
避免超时的方式是特判:未知进制数是1位和两位的情况
- 如果未知进制数是一位,无论几进制均是其本身只需比较ans与一位未知进制数。
- 洳果未知进制数是两位由于最末位数字不影响比较,那么需判断首位数字c[0]与ans(ans=ans-未知进制数最末位上的数)能否组成倍数关系其倍数也僦是进制数。例:已知数字的十进制为11未知进制数是32(减掉最末位11→9、9/3=3 但是三进制中最大数字为2,所有不可能相等);再例如:十进制為11未知进制是23(减掉最末位11→8、8/2=4并且2和3均小于4,故23在4进制的条件下等于11)
//特判未知进位数为一位和两位否则会超时。 //进制从未知数的朂大一位上的数字+1开始跑