题解 P4984 【转换】

hdxrie · 2018-10-17 16:22:15 · 题解

注意：

这里默认大家都会整数在正进制之间的转换。

题解时间复杂度中所提到的m表示转换前价格串的最长长度，k表示转换后价格串的最长长度，p表示总共需要转换的次数。

算法1：

观察数据范围，发现只有整数之间的转换，且进制都为正，那么直接写就行了，属于送分版块。

时间复杂度O(m+kp)，期望得分：5分。

算法2：

加入了负进制后，这个部分可以参照P1017 进制转换。

我们先依然按照原来正进制的方法转换，现在的问题就是有些位上会是负数，例如：7(10进制)转成-2进制后，变成了1-11，那为负的位应该怎样处理？还是上面的例子，现在是(-2)^1这一位为负，也就是说，我们想要一个(-2)^1\times(-1)，但是由于进制位上不能为负，考虑转化：(-2)^1\times(-1)=(-2)^2\times1+(-2)^1\times1，可以看到我们把前一位加1，那么相当于对当前这一位加上了2，总结来说：若将前一位加1，则当前位加上|a|。

但是有了加，也就有了进位操作，但是与正进制相反的是，负进制的进位是减。以上面为例，借位以后变成了211(-2进制)，(-2)^2\times2明显不是合法的，需要进位，(-2)^2\times2=(-2)^3\times(-1)，可以看到进位变成了减，总结来说：若将前一位减1，则当前位减去|a|。

根据上面的两个方法，把负数位变成正数就行，那么7(10进制)转成-2进制后应该为11011。

时间复杂度O(m+kp)，期望得分：15分。

算法3：

现在有了小数部分，并且保证转换前后都是有限小数，而且进制都为正，那么现在的问题是如何计算小数部分。

以8进制下的小数0.67转16进制为例：

考虑先把小数部分转化为10进制的分数形式，那么表示成10进制下的分数形式为\frac{6\times8^1+7\times8^0}{8^2}=\frac{55}{64}。

虽然我们不清楚该分数在16进制下的具体值，但是我们可以知道它一定可以转换成这样的形式：16^0\times a_0+16^{-1}\times a_1+16^{-2}\times a_2+\cdots，我们现在想知道所有a的具体值，那么可以用类似于整数的转换方式，先对整个数乘上进制a，这样就把-1次位提到了0次位，其它位以此类推，然后再用向下取整提取0次位的值，再去掉0次位的值，这样一直做下去，直到变成0，就能提出所有小数位。

为了方便理解，这里模拟一下上面的例子：

第一个小数位：\left\lfloor\frac{55\times 16}{64}\right\rfloor=13，下一位为\frac{55\times 16}{64}-13=\frac{48}{64}；

第二个小数位：\left\lfloor\frac{48\times 16}{64}\right\rfloor=12，下一位为\frac{48\times 16}{64}-12=0；

所以转换为16进制后，变成了\rm 0.DC。

其它进制转换同理。

时间复杂度O(m+kp)，期望得分：30分。

算法4：

有了循环小数，但是进制还是全部为正，依然考虑先将循环小数改为分数形式，下面先给结论：

假设在k进制下有一个无限循环小数，其循环节长度为p，令x表示将循环节看成k进制下的整数再转化为10进制后的值，其不循环部分长度为q，令y表示将不循环部分看成k进制下的整数再转化为10进制后的值，那么在10进制下，其分数形式为：

以10进制下的无限循环小数0.4<230769>为例：

那么循环节长度p=6，看成10进制整数为x=230769，非循环部分长度为q=1，看成10进制整数为y=4。

那么10进制下的分数形式为:\frac{230769}{(10^6-1)\times 10}+\frac{4}{10}=\frac{4230765}{9999990}=\frac{11}{26}

其它进制下的无限循环小数同理。

下面是复杂的证明，但是好像有更简单的证明：

以\frac{3}{7}转化成5进制下的小数的为例，可以知道转换后的答案为0.<203241>。

由于循环小数是循环的，也就是说我们在对每一个分数位提取的时候，它的分数形式是一个循环，下面给出例子的每一个小数位提取时的分数形式（即向下取整之前的分数形式）：\frac{3}{7},\frac{1}{7},\frac{5}{7},\frac{4}{7},\frac{6}{7},\frac{2}{7},\frac{3}{7},\frac{1}{7}\cdots可以看到每6位一次循环。

令p表示循环节长度，如果我们不一位一位的提取，而是一次直接提取p位，那分数形式就会全部一样了，以上面为例：直接提取6位小数，则整数部分为\left\lfloor\frac{3\times 5^6}{7}\right\rfloor=6696，将6696转为5进制为203241（之前一位一位提取不用转进制是因为向下取整后一定在0次位上），然后\frac{3\times 5^6}{7}-6696=\frac{3}{7}，可以看到又变成原来的样子了，那么假设该无限循环小数是k进制的，且由\frac{x}{y}得出，且循环节长度为p，且循环节转换为10进制后值为v，那么可以得到下面这个等式：

因为\left\lfloor\frac{x\times k^p}{y}\right\rfloor=v可以直接计算，所以公式移项变形后为：

这样我们就成功得到了任意进制下的无限循环小数转10进制分数的公式。

但是还不够，如果这种情况0.4<230769>，循环节没有包含所有小数部分，上面那个公式并不能完美解决，实际上我们直接拆开0.4<230769>=0.4+\frac{0.<230769>}{10}，我们只需要计算0.<230769>的分数形式，剩下的直接通分合并就行，这样就有了我们一开始所提出的公式：

这样我们就可以将无限小数转分数了，并且证明中途提到了，如果提位中途发现和前面的分数形式有重复，则出现了循环节，那么我们可以用\rm Hash判断状态是否出现，并且出现在哪一个小数位，这样就可以判断循环小数了。

时间复杂度O(m+kp)，期望得分：50分。

算法5：

对于负进制的循环小数转分数，上面的公式依然适用。但是转负进制小数也有和转整数一样的问题，就是借位和进位，而且要注意的是借位和进位操作有时还会影响到整数位，不能像之前一样整数和小数分开考虑。如果小数位是有限小数，那么每一次直接暴力借位和进位就行，但是循环小数如果出现借位或进位操作会对之前的分数形式造成影响，那么该如判断循环节？

如果不知道为什么进位或借位会对分数形式造成影响，在这里解释一下：

假设当前我们要转成一个a进制小数，现在考虑到某个小数位，其前一个小数位的分数形式为\frac{x}{y}，前一位的值为b，由于我们得到某一位的分数形式是用上一位的分数形式乘进制再减去上一位的值，所以我们当前这一位的分数形式为\frac{x\times a}{y}-b，但是如果你发现当前需要进位，即前一位减1，那么b就会少1，当前这位的分数形式也就相应的发生了变化，借位同理。

这个实际上很好解决，由于答案长度保证不超过\left\lfloor\log_{|a|}2^{62}\right\rfloor，我们只需要先求出所有可能的的小数位的分数形式，然后再从头往后扫一遍看分数形式是否重复就行了，但是这样想实际上还是错的。

我们说过，负进制存在借位和进位操作，所以第二个循环节可能会对第一个循环节造成影响，从而改变第一个循环节某一位的值，所以需要再多往后找一个循环节，这样就保证了第一个循环节的影响全部被考虑完了，也就是说值是固定的了。

但是为什么只需要向后再找一个循环节？下面将证明最多只会有第二个循环节对第一个循环节产生影响。

为了方便证明，实际上我们只需要考虑一个循环节会对前面一位造成什么影响，就可以判断整个情况了，因为这是一个循环节的影响，并且所有循环节又是相同的，所以每一个循环节对前一位的影响都是相同的，那么我们只需要证明那些更远的循环节会对第一个循环节造成影响的情况不存在就行。

如果没听懂什么是“一个循环节对前面一位造成的影响”的话，在这里举个例子：假如说我们要将\frac{-1}{12}转成-4进制，那么答案为0.1<32>，为了找到一个循环节对前一位的影响，我们只加入一个循环节的值，其它的都不加，并且若进位或借位出现在循环节外面，就不管。这样计算下来就会得到0.1\underline{31}，也就是说，这个例子中一个循环节会对前一个小数位造成1的影响。

可以证明所有情况下一个循环节对前面的影响只有-1,0,1这三种，其它的情况都是不合法的，这个很好理解，就不在这里证明了。

考虑怎样让更远的循环节对第一个循环节造成影响，这个需要对循环节长度分奇偶讨论：

循环节长度为偶数时，假如是转a进制，那么只有填完一个循环节，出现类似于0.-1\ \underline{(|a|-1)\ 0}和0.1\ \underline{0\ (|a|-1)}这样的，那么才有可能因为第三个循环节的加入，使得第二个循环节最后一个位置的值发生改变然后影响一直传递，导致第一个循环节发生更改。

我们把加入了三个循环节的情况手动模拟出来看一下：

可以看到，继续加循环节已经不会对第一个循环节造成影响，但是第三个循环节确实对第一个循环节造成了影响，但是这种情况是不存在的，注意前面的-2，我们之前说过，进位或借位只会有-1,0,1这三种，但是这里却出现了-2，所以这是不合法的。