對(duì)大數(shù)的進(jìn)制轉(zhuǎn)換，可以不用大數(shù)的除法運(yùn)算。
假設(shè)要把一個(gè)二進(jìn)制數(shù)1011，轉(zhuǎn)換成一個(gè)三進(jìn)制數(shù)。
1、用二進(jìn)制數(shù)的第一位1去除以3，商為0，余數(shù)是1
2、由于前面一位的除法結(jié)果有余數(shù)，所以要把余數(shù)*(進(jìn)制)+該為數(shù)字。對(duì)于本例，就是1(余數(shù))*2(進(jìn)制)+0(當(dāng)前這位的數(shù)值)=2。除以3后，商0，余數(shù)是2
3、同2所述，2(余數(shù))*2(進(jìn)制)+1(當(dāng)前這位的數(shù)值)=5。5除以3后，商1，余數(shù)2
4、同2所述，2(余數(shù))*2(進(jìn)制)+1(當(dāng)前這位的數(shù)值)=5。5除以3后，商1，余數(shù)2
以上四步可以表示為 1011(2-based) / 3(要轉(zhuǎn)換成的基數(shù)) = 0011(2-based 商).. 2(3-based 余數(shù))
然后再讓0011除以3，重復(fù)以上步驟，直到商為0。每次的余數(shù)的逆序就是以3為基的數(shù)。
1011/3 -->0011 ..2
0011/3 -->0001 ..0
0001/3 -->0000 ..1
所以，1011(2-based) --> 102(3-based)
參考http://acm.pku.edu.cn/JudgeOnline/problem?id=1220
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
char index[62] = {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd',
'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
'y', 'z'};
int getValue(char ch)
{
if(ch>='0'&&ch<='9') return ch-'0';
else if(ch>='A'&&ch<='Z') return ch-'A'+10;
else return ch-'a'+36;
}
string change(int from,int to,string input)
{
string res="",tmp="";
int remainder,pos;
while(input.length()!=0)
{
remainder=0;
for(pos=0;pos<input.length();pos++)
{
remainder=remainder*from+getValue(input[pos]);
if(remainder<to)
{
tmp=tmp+'0';
continue;
}
else
{
tmp=tmp+index[remainder/to];
remainder%=to;
}
}
res=index[remainder]+res;
for(pos=0;pos<tmp.length()&&tmp[pos]=='0';pos++);
input=tmp.substr(pos);
tmp="";
}
return res;
}
int main()
{
int t,from,to;
string num;
cin>>t;
while(t--)
{
cin>>from>>to>>num;
cout<<from<<" "<<num<<endl;
cout<<to<<" "<<change(from,to,num)<<endl<<endl;
}
}