11届中南林业校赛 神奇的进制转换

链接：https://ac.nowcoder.com/acm/contest/910/C 来源：牛客网

神奇的进制转换

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld

题目描述

给出一个m进制下的数a，现在请输出a在n进制下的表示。

输入描述:

第一行一个整数T，代表有T组数据 接下来T行： 每一行有3个整数，分别表示m，n，a，其中2=<m<=62，2=<n<=62，a的位数不超过350位且a>=0，样例个数不超过400。

输出描述:

输出上述问题的答案，每个答案占一行。

示例1

输入

复制

1 10 2 3

输出

复制

11

备注:

每一位进制表示从小到大分别为 0~9, 'A'~'Z', 'a'~'z'

---

大数取余是个难点 

#include<bits/stdc++.h> #define MAXN 9999 #define M 1000 #define DLEN 4 #define lom long long using namespace std; class Bint { private: int a[M]; int len; public: Bint()//Construction function { len=1; memset(a,0,sizeof(a)); } Bint(const int); Bint(const char*); Bint(const Bint &); Bint(const std::string s); friend istream & operator>>(istream&, Bint&);//Overloaded IO stream friend ostream & operator<<(ostream&, Bint&); Bint &operator=(const Bint &);//Overloaded operator Bint operator+(const Bint &) const; Bint operator-(const Bint &) const; Bint operator*(const Bint &) const; Bint operator/(const int &) const; Bint operator^(const int &) const; int operator%(const int &) const; bool operator<(const Bint& b)const { if(len!=b.len)return len<b.len; for (int i=len-1; i>=0; --i)if(a[i]!=b.a[i])return a[i]<b.a[i]; return false; } bool operator>(const Bint& b)const { return b<*this; } bool operator<=(const Bint& b)const { return !(b<*this); } bool operator>=(const Bint& b)const { return !(*this<b); } bool operator!=(const Bint& b)const { return b<*this||*this<b; } bool operator==(const Bint& b)const { return !(b<*this)&&!(*this<b); } void print()//output { printf("%d",a[len-1]); for(int i=len-2; i>=0; --i)printf("d",a[i]); putchar('\n'); }; }; Bint::Bint(const int b) { int c,d=b; len=0; memset(a,0,sizeof(a)); while(d>MAXN) { c=d-(d/(MAXN+1))*(MAXN+1); d=d/(MAXN+1); a[len++]=c; } a[len++]=d; } Bint::Bint(const char*s) { int t,k,index,l,i; memset(a,0,sizeof(a)); l=strlen(s); len=l/DLEN; if(l%DLEN) ++len; index=0; for(i=l-1; i>=0; i-=DLEN) { t=0; k=i-DLEN+1; if(k<0)k=0; for(int j=k; j<=i; j++)t=t*10+s[j]-'0'; a[index++]=t; } } Bint::Bint(const Bint & T):len(T.len) //拷贝构造函数 { memset(a,0,sizeof(a)); for(int i=0; i<len; ++i) a[i]=T.a[i]; } Bint::Bint(const std::string s) { int t,k,index,l,i; memset(a,0,sizeof(a)); l=s.length(); len=l/DLEN; if(l%DLEN) ++len; index=0; for(i=l-1; i>=0; i-=DLEN) { t=0; k=i-DLEN+1; if(k<0)k=0; for(int j=k; j<=i; j++)t=t*10+s[j]-'0'; a[index++]=t; } } Bint & Bint::operator=(const Bint & n) //重载赋值运算符，大数之间进行赋值运算 { len=n.len; memset(a,0,sizeof(a)); for(int i=0; i<len; ++i)a[i]=n.a[i]; return *this; } istream& operator>>(istream & in,Bint & b) { char ch[M*4]; in>>ch; int l=strlen(ch),count=0,sum=0,i=-1; for(int i=l-1; i>=0;) { sum=0; int t=1; for(int j=0; j<4&&i>=0; ++j,--i,t*=10)sum+=(ch[i]-'0')*t; b.a[count]=sum; ++count; } b.len=count++; return in; } ostream& operator<<(ostream& out,Bint& b) //重载输出运算符 { cout<<b.a[b.len-1]; for(int i=b.len-2; i>=0; --i) { cout.width(DLEN); cout.fill('0'); cout<<b.a[i]; } return out; } Bint Bint::operator+(const Bint & T) const { Bint t(*this); int i,big; //位数 big=T.len>len?T.len:len; for(i=0; i<big; ++i) { t.a[i]+=T.a[i]; if(t.a[i]>MAXN) { ++t.a[i+1]; t.a[i]-=MAXN+1; } } if(t.a[big]!=0)t.len=big+1; else t.len=big; return t; } Bint Bint::operator-(const Bint & T) const { int i,j,big; bool flag; Bint t1,t2; if(*this>T) { t1=*this; t2=T; flag=0; } else { t1=T; t2=*this; flag=1; } big=t1.len; for(i=0; i<big; ++i) if(t1.a[i]<t2.a[i]) { j=i+1; while(t1.a[j]==0)++j; --t1.a[j--]; while(j>i)t1.a[j--]+=MAXN; t1.a[i]+=MAXN+1-t2.a[i]; } else t1.a[i]-=t2.a[i]; t1.len=big; while(t1.a[len-1]==0&&t1.len>1)--t1.len,--big; if(flag)t1.a[big-1]=0-t1.a[big-1]; return t1; } Bint Bint::operator*(const Bint & T) const { Bint ret; int i,j,up; int temp,temp1; for(i=0; i<len; ++i) { up=0; for(j=0; j<T.len; ++j) { temp=a[i]*T.a[j]+ret.a[i+j]+up; if(temp>MAXN) { temp1=temp-temp/(MAXN+1)*(MAXN+1); up=temp/(MAXN+1); ret.a[i+j]=temp1; } else up=0,ret.a[i + j]=temp; } if(up!=0)ret.a[i+j]=up; } ret.len=i+j; while(ret.a[ret.len-1]==0&&ret.len>1) --ret.len; return ret; } Bint Bint::operator/(const int & b) const { Bint ret; int i,down=0; for(i=len-1; i>=0; --i) { ret.a[i]=(a[i]+down*(MAXN+1))/b; down=a[i]+down*(MAXN+1)-ret.a[i]*b; } ret.len=len; while(ret.a[ret.len-1]==0&&ret.len>1)--ret.len; return ret; } int Bint::operator %(const int & b) const { int i,d=0; for (i=len-1; i>=0; --i)d=((d*(MAXN+1))%b+a[i])%b; return d; } Bint Bint::operator^(const int & n) const { Bint t,ret(1); if(n<0)exit(-1); if(n==0)return 1; if(n==1)return *this; int m=n,i; while(m>1) { t=*this; for(i=1; i<<1<=m; i<<=1)t=t*t; m-=i; ret=ret*t; if(m==1)ret=ret*(*this); } return ret; } int turn(char c) { if(c>='0'&&c<='9') return c-'0'; else if(c>='A'&&c<='Z') return c-'A'+10; return c-'a'+36; } const string T="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; string slove(int x,int y,string s) { Bint sum; int temp; string res=""; lom len=s.length(); for(char c:s) sum=sum*x+turn(c); while(sum>0) { res=T[sum%y]+res; sum=sum/y; } if(res.length()==0) return "0"; else return res; } int main() { int t; string s; cin>>t; while(t--) { int m,n; cin>>m>>n>>s; cout<<slove(m,n,s)<<endl; } return 0; }