U249090 密码门 私题题解

· · 题解

题目传送门

题目简要翻译

输入第一行一个询问次数 t，然后是输出的进制 n，接下来每一行都有 c 进制的 a 和 d 进制的 b，输出 a 与 b 的各种运算结果（题目上那四种运算）并用 n 进制表示。

思路

数据超水，暴力模拟就能过。

先用题目上所给公式将所给数字转为十进制，再进行十进制运算，最后转化为 n 进制结果输出。

那么问题来了：一个数字怎么由十进制转 n 进制？

证明

例：对于一个 n 进制数 (\overline{abcde})_ {n}=(x)_ {10} 一定能写成

x = an^4+bn^3+cn^2+dn+e

的形式，其中低项系数严格小于高项参数（e<n,d<n^2,c<n^3,b<n^4,a<n^5）,我们要把这个十进制数转化为 n 进制数，相当于知道这个多项式的结果反求系数，设这个多项式的结果为 x，由于 e<n 我们可以通过 x\%n 来得到 e，将这个数存下来以后，整个我们将 x 整除 n，得到

x=an^3+bn^2+cn+d

再将这个多项式继续如上处理，直到 x 不能整除 n 为止，就能将这个多项式各位上的系数依次记录下来，然后输出即可。

void pr(__int128 ans)
{
    if(ans==0)//一定要判，否则会RE
    {
        wr(0);
        return;
    }
    int lans=0;
    for(int i=1;ans;ans/=n,i++)
    {
        sans[i]=ans%n;
        lans=i;
    }
    for(int i=lans;i;i--)
    {
        if(sans[i]>=10&&sans[i]<=35)
            sans[i]=sans[i]-10+'a';
        else if(sans[i]>=36&&sans[i]<=61)
            sans[i]=sans[i]-36+'A';
        else
            sans[i]+='0';
        putchar(sans[i]);
    }

转化十进制的过程直接套题目中给出的公式即可。

注意

对于 100\% 的数据，1\le t\le 5\times10^{4} , 2\le n ,c_i,d_i\le 61 , 1\le m\le 2 \times 10^{17}。

这里在相乘的过程中可能会炸 long long，所以要开 __int128才能过。

代码

int t,n,a,b,na,nb;
__int128 ans;
char sa[700],sb[700],sans[1300];
void pr(__int128 ans)
{
    if(ans==0)
    {
        wr(0);
        return;
    }
    int lans=0;
    for(int i=1;ans;ans/=n,i++)
    {
        sans[i]=ans%n;
        lans=i;
    }
    for(int i=lans;i;i--)
    {
        if(sans[i]>=10&&sans[i]<=35)
            sans[i]=sans[i]-10+'a';
        else if(sans[i]>=36&&sans[i]<=61)
            sans[i]=sans[i]-36+'A';
        else
            sans[i]+='0';
        putchar(sans[i]);
    }
}
signed main()
{
    t=re(),n=re();
    while(t--)
    {
        na=re(),nb=re();
        a=b=0;
        cin>>sa+1,cin>>sb+1;
        int la=strlen(sa+1),lb=strlen(sb+1);
        for(int i=la;i;i--)
        {
            if(sa[i]>='a'&&sa[i]<='z')
                sa[i]-='a'-11;
            else if(sa[i]>='A'&&sa[i]<='Z')
                sa[i]-='A'-37;
            else if(sa[i]>='0'&&sa[i]<='9')
                sa[i]-='0';
        }
        for(int i=lb;i;i--)
        {
            if(sb[i]>='a'&&sb[i]<='z')
                sb[i]-='a'-10;
            else if(sb[i]>='A'&&sb[i]<='Z')
                sb[i]-='A'-36;
            else if(sb[i]>='0'&&sb[i]<='9')
                sb[i]-='0';
        }
        for(int i=1;i<=la;i++)
            a+=sa[i]*pow(na,la-i);
        for(int i=1;i<=lb;i++)
            b+=sb[i]*pow(nb,lb-i);
        ans=a+b,pr(ans),putchar(' ');
        ans=abs(a-b),pr(ans),putchar(' ');
        ans=(__int128)a*b,pr(ans),putchar(' ');
        ans=a%b,pr(ans),putchar('\n');
    }
    return 0;
}