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

el/2023/6/3 17:07:59

链接: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 streamfriend ostream & operator<<(ostream&,  Bint&);Bint &operator=(const Bint &);//Overloaded operatorBint  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("%04d",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;
}

 

http://www.ngui.cc/el/3419488.html

相关文章

第11届中南林业校赛 0和5

链接&#xff1a;https://ac.nowcoder.com/acm/contest/910/G 来源&#xff1a;牛客网 小C手中有n张牌&#xff0c;每张牌上有一个一位数的数&#xff0c;这个数字不是0就是5。 小C从这些牌在抽出任意张&#xff08;不能抽0张&#xff09;&#xff0c;排成一行就组成了一个…

牛客赛47 DongDong认亲戚(并查集+map)

链接&#xff1a;https://ac.nowcoder.com/acm/contest/904/B 来源&#xff1a;牛客网 题目描述 DongDong每年过春节都要回到老家探亲&#xff0c;然而DongDong记性并不好&#xff0c;没法想起谁是谁的亲戚&#xff08;定义:若A和B是亲戚&#xff0c;B和C是亲戚&#xff0c…

计算机组成原理复习篇

第一章 1、说明高级语言、汇编语言和机器语言的差别及其联系 机器语言是计算机硬件能够直接识别的语言&#xff0c;汇编语言是机器语言的符号表示&#xff0c;高级语言是面向算法的语言。高级语言编写的程序&#xff08;源程序&#xff09;处于最高层&#xff0c;必须翻译成汇…

hdu 2572 终曲(暴力匹配)

最后的挑战终于到了&#xff01; 站在yifenfei和MM面前的只剩下邪恶的大魔王lemon一人了&#xff01;战胜他&#xff0c;yifenfei就能顺利救出MM。 Yifenfei和魔王lemon的挑战很简单&#xff1a;由lemon给出三个字符串&#xff0c;然后要yifenfei说出第一串的某个子串&#x…

hdu2086 A1 = ? (数学)

Problem Description 有如下方程&#xff1a;Ai (Ai-1 Ai1)/2 - Ci (i 1, 2, 3, .... n). 若给出A0, An1, 和 C1, C2, .....Cn. 请编程计算A1 ? Input 输入包括多个测试实例。 对于每个实例&#xff0c;首先是一个正整数n,(n < 3000); 然后是2个数a0, an1.接下来的n行…

牛客小白月赛16小阳买水果(前缀和+贪心)

链接&#xff1a;https://ac.nowcoder.com/acm/contest/949/D 来源&#xff1a;牛客网 题目描述 水果店里有 nnn个水果排成一列。店长要求顾客只能买一段连续的水果。 小阳对每个水果都有一个喜爱程度 aia_iai​&#xff0c;最终的满意度为他买到的水果的喜欢程度之和。 如…

牛客小白月赛16 小雨的矩阵 (暴力搜索)

链接&#xff1a;https://ac.nowcoder.com/acm/contest/949/E 来源&#xff1a;牛客网 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 小雨有一个 nnn \times nnn 的矩…

牛客小白月赛16 小石的妹子 (贪心 )

链接&#xff1a;https://ac.nowcoder.com/acm/contest/949/F 来源&#xff1a;牛客网 小石的妹子 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 小石有 n 个妹子&a…

牛客 回文数(模拟 )

链接&#xff1a;https://ac.nowcoder.com/acm/contest/1071/A 来源&#xff1a;牛客网 题目描述 今年是国际数学联盟确定的“2000——世界数学年”&#xff0c;又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛&#xff0c;组织了一场别开生面的数学…

牛客Game with numbers(暴力)

链接&#xff1a;https://ac.nowcoder.com/acm/contest/942/B 来源&#xff1a;牛客网 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 给定大小为n{n}n的集合S{S}S 一…