高精度进制转换（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\n",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]='\0';

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&m,&n);

        scanf("%s",iput);

        printf("%d %s\n",m,iput);

        solve();

        printf("%d %s\n\n",n,oput);

        memset(niput,0,sizeof(niput));

        memset(niput,0,sizeof(oput));

    }

    return 0;

}