自动搬运

查看原文

来自洛谷，原作者为

	hdxrie **

搬运于2025-08-24 22:05:54，当前版本为作者最后更新于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$进制下，其分数形式为：

$$\frac{x}{(k^p-1)\times k^q}+\frac{y}{k^q}$$

以$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$，那么可以得到下面这个等式：

$$\frac{x\times k^p}{y}-\left\lfloor\frac{x\times k^p}{y}\right\rfloor=\frac{x}{y} $$

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

$$\frac{x}{y}=\frac{v}{k^p-1}$$

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

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

$$\frac{x}{(k^p-1)\times k^q}+\frac{y}{k^q}$$

这样我们就可以将无限小数转分数了，并且证明中途提到了，如果提位中途发现和前面的分数形式有重复，则出现了循环节，那么我们可以用$\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)}$这样的，那么才有可能因为第三个循环节的加入，使得第二个循环节最后一个位置的值发生改变然后影响一直传递，导致第一个循环节发生更改。

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

$$0.-2\ \underline{0\ (|a|-2)}\ \underline{0\ (|a|-1)}\ \underline{(|a|-1)\ 0} $$

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

$0.1\ \underline{0\ (a-1)}$这种情况的证明同理。

循环节长度为奇数时，只有$0.-1\ \underline{0\ (a-1)\ 0}$和$0.1\ \underline{(a-1)\ 0\ (a-1)}$这两种情况会产生影响，但是如果手动模拟会发现，每加一个循环节都会对前面所有的循环节造成影响，也就是说循环节根本不能被确定，也就不存在循环节这一说，所以这种情况也不合法。（个人感觉这里的证明有点牵强，希望有大佬能给出更好的证明）

所以只需要找两个循环节就可以考虑完其它小数位对第一个循环节的所有影响，那么这道题就解决了。

由于存在进位和借位操作，所以不同进制的转换时间复杂度波动较大，令$w$表示一次转换操作中借位和进位操作所造成的复杂度，可以估计一下$w$应该是$k$的常数倍左右，那么时间复杂度为$O(m+kp+wp)$，期望得分：$100$分。

当然还有其它细节问题，自己注意一下就好了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=550,mod=294703,seed=761153;
char pri[N];
LL ls,val,up,up1,up2,down,down1,down2,sta[N][2];
int T,l,r,k,len,num,now,all,out,ans[N],mer[N],head[mod];
struct Hash
{
    LL a,b;int bef,pos;
}ln[N];
LL gcd(LL a,LL b)
{
    if(!b)return a;
    return gcd(b,a%b);
}
void clear(LL v1,LL v2)
{
    int a=(v1%mod*seed%mod+v2%mod)%mod;
    if(a<0)a+=mod;head[a]=0;
}
void add(LL v1,LL v2,int now)
{
    int a=(v1%mod*seed%mod+v2%mod)%mod;
    if(a<0)a+=mod;ln[++k].a=v1;ln[k].b=v2;
    ln[k].pos=now;ln[k].bef=head[a];head[a]=k;
}
int check(LL v1,LL v2)
{
    int a=(v1%mod*seed%mod+v2%mod)%mod;
    if(a<0)a+=mod;
    for(int i=head[a];i;i=ln[i].bef)
     if(ln[i].a==v1&&ln[i].b==v2)
      return ln[i].pos;
    return -1;
}
LL multi(LL a,LL b,LL c,int &p)
{
    LL ans=0,val=0;if(b<0)b=-b,a=-a;
    for(LL d=0;b;b>>=1,d+=d+(a+a)/c,a=(a+a)%c)
     if(b&1)val+=d+(ans+a)/c,(ans+=a)%=c;
    p=val;return ans;
}
void Integer_change(int a)
{
    ls=val;int p=0,q=0;
    if(a>0&&ls<0)ls=-ls;
    while(ls||!now)
    {
        p=ls%a;ls/=a;p+=q;q=0;
        if(p<0)p-=a,q++;
        q+=p/a;p%=a;ans[++now]=p;
    }
    if(q!=0)
    {
        if(q>0)ans[++now]=q;
        else ans[++now]=q-a,ans[++now]=1;
    }
}
void Decimal_change(int a)
{
    int pos=-1,en=0;
    up1=up;down1=down;k=0;
    if(a>0)
    {
        up1=abs(up1);len=0;
        while(1)
        {
            pos=check(up1,down1);
            if(pos!=-1){en=len;break;}
            else add(up1,down1,len+1);
            sta[++len][0]=up1;sta[len][1]=down1;
            up1=multi(up1,a,down1,mer[len]);
            if(!up1){en=len;break;}
        }
    }
    else
    {
        for(int i=1;i<=130;i++)
        {
            sta[i][0]=up1;sta[i][1]=down1;
            up1=multi(up1,a,down1,mer[i]);
            for(int j=i;j>=1;j--)
            {
                if(mer[j]>=0&&mer[j]<(-a))break;
                if(sta[j][0]>0)sta[j][0]-=sta[j][1];
                else sta[j][0]+=sta[j][1];
                mer[j-1]+=mer[j]/a;mer[j]%=a;
                if(mer[j]<0)mer[j-1]++,mer[j]=mer[j]-a;
            }
            if(!up1){en=i;break;}
        }
        if(!en)
        for(int i=1;i<=63;i++)
        {
            pos=check(sta[i][0],sta[i][1]);
            if(pos!=-1){en=i-1;break;}
            add(sta[i][0],sta[i][1],i);
        }
        if(mer[0]!=0)
        {
            ans[1]+=mer[0];
            for(int i=1;i<=now;i++)
            {
                if(ans[i]>=0&&ans[i]<-a)break;
                ans[i+1]+=ans[i]/a,ans[i]%=a;
                if(ans[i]<0)ans[i+1]++,ans[i]=ans[i]-a;
            }
            if(ans[now+1]!=0)
            {
                if(ans[now+1]>0)now++;
                else
                {
                    now++;ans[now]=ans[now]-a;
                    ans[now+1]=1;now++;
                }
            }
        }
    }
    if(out)printf("-");
    while(now)
    {
        if(ans[now]<10)printf("%d",ans[now]);
        else printf("%c",ans[now]-10+'A');
        ans[now--]=0;
    }
    printf(".");
    for(int i=1;i<=en;i++)
    {
        clear(sta[i][0],sta[i][1]);
        if(i==pos)printf("<");
        if(mer[i]<10)printf("%d",mer[i]);
        else printf("%c",mer[i]-10+'A');
        mer[i]=0;
    }
    if(pos!=-1)printf(">");mer[0]=0;
    return;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        val=up1=up2=0;
        all=down1=down2=1;int poi=0,flag=0;
        scanf("%d%d%d%s",&num,&l,&r,pri+1);
        len=strlen(pri+1);
        for(int i=1;i<=len;i++)
        {
            if(pri[i]=='.'){poi=i;break;}
            if(pri[i]=='-'){all=-1;continue;}
            if(pri[i]>='A')val=val*num+pri[i]-'A'+10;
            else val=val*num+pri[i]-'0';
        }
        if(poi)for(int i=poi+1;i<=len;i++)
        {
            if(pri[i]=='<'){flag=1;continue;}
            if(pri[i]=='>')break;
            if(!flag)
            {
                if(pri[i]>='A')up1=up1*num+pri[i]-'A'+10;
                else up1=up1*num+pri[i]-'0';down1*=num;
            }
            else
            {
                if(pri[i]>='A')up2=up2*num+pri[i]-'A'+10;
                else up2=up2*num+pri[i]-'0';down2*=num;
            }
        }
        if(!flag)up=up1,down=down1;
        else
        {
            down2=(down2-1)*down1;ls=gcd(down1,down2);
            up=down1/ls*up2+down2/ls*up1;down=down1/ls*down2;
        }
        up*=all;val*=all;
        if(poi)
        {
        	LL ok=gcd(up,down);up/=ok;down/=ok;
        	if(down<0)down=-down,up=-up;
            if(val>0&&up<0)val--,up+=down;
            if(val<0&&up>0)val++,up-=down;
        }
        for(int i=l;i<=r;i++)
         if(abs(i)>1)
         {
         	if(i>0&&(val<0||up<0))out=1;else out=0;
         	Integer_change(i);
         	if(poi)Decimal_change(i);
         	else
            {
                if(out)printf("-");
                while(now)
                {
                	if(ans[now]<10)printf("%d",ans[now]);
                	else printf("%c",ans[now]-10+'A');
                	ans[now--]=0;
                }
            }
            printf("\n");
         }
    }
    return 0;
}