高精度进制转换（poj1220）

常规短除法原理

高精度进制转换是对于特别大的数字来说的，当数字特别大时，难以进行除法和取余的操作，此时通过字符串模拟的办法可以解决。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2000 + 5;

int niput[maxn];
int noput[maxn];
char iput[maxn]; //原数字
char oput[maxn]; //转换后的数字
int m,n; //原进制，转换后的进制

char num_to_char(int val)//数字与字符对应关系 A-Z对应10-36 a-z对应37-62
{
    if(val>=0&&val<=9)return val+'0';
    if(val>=10&&val<=35)return val-10+'A';
    return val-36+'a';
}

int char_to_num(char ch)
{
    if(ch>='0'&&ch<='9') return ch-'0';//数字 
    if(ch>='A'&&ch<='Z') return ch-'A'+10;//大写字母 
    return ch-'a'+36;           //小写字母 
}

void solve()
{
    int re=0,qu;//余数 商
    int len=strlen(iput);
    for(int i=0;i<len;i++) niput[i]=char_to_num(iput[i]);
    int cnt=0;       //转换后的长度
    int idx=0;       //遍历字符串的下标
    while(idx<len)   //当下标等于长度时，说明遍历完了
    {
        for(int i=idx;i<len;i++)
        {
        qu=(niput[i]+m*re)/n;
        re=(niput[i]+m*re)%n;
        //printf("%d %d
",qu,re);
        niput[i]=qu;
        }
        oput[cnt++]=num_to_char(re);
        re=0;
        while(niput[idx]==0)   //去除前导0
        idx++;
    }
    reverse(oput,oput+cnt);  //左闭右开，翻转
    oput[cnt]='';
}

int main() 
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        scanf("%s",iput);
        printf("%d %s
",m,iput);
        solve();
        printf("%d %s

",n,oput);
        memset(niput,0,sizeof(niput));
        memset(niput,0,sizeof(oput));
    }
    return 0;
}