题目传送门
题目简要翻译
输入第一行一个询问次数 \(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';elsesans[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';elsesans[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;
}