poj 1220（短除法）

http://poj.org/problem?id=1220

题意：进制转换，把a进制转换为b进制。

如果数据不大的话，那么这个题还是很简单的，但这个题就是数据范围太大，所以这里可以采用短除法来做。

关于短除法，就是把每一位（这里指的每一位是指个位十位之类的）除以要转换的进制的余数在乘以当前进制的值加到下一位去，当前位的值就为商，然后这样一直进行到最后一位（也就是个位）个位在对所须转换的进制在取模，那么这个模就是转换后的结果。多次重复，直到最后一位为0，从后往前看就是答案。

举个例子：50，要从十进制转换为二进制。

十位是5，个位是0，那么首先5/2商为2，余1

下一步就是1*10+0=10，然后个位就变成了10，然后10/2=5余0，0就是结果的个位，

然后下一步就是对25进行操作

2/2商1余0，那么十位就是1，个位就是0*10+5=5.

5/2商2余1，那么结果的十位就是1。

然后对12进行操作，十位是1，1/2商0余1，那么十位就为0了。

个位就是1*10+2=12.12/2商6余0，结果的百位就是0.

因为十位是0，所以只对个位进行操作了，6/2商3余0，千为就是0

3/2商1余1，万位为1.

1/2商0余1，十万位为1，所以50转换为二进制就是110010

#include <stdio.h>
#include <string.h>
#define l 600

int a,b,ans[l],tmp[l];
char c[l];

int main()
{
    int n,k;
    scanf("%d",&n);
    while(n--)
    {
        memset(tmp,0,sizeof(tmp));
        memset(ans,0,sizeof(ans));
        memset(c,0,sizeof(c));
        scanf("%d%d%s",&a,&b,c);
        int len=strlen(c);
        for(int i=0,m=len-1;i<len;i++,m--){      //这里要注意，要把最低位放在tmp[0]，因为始终是取最低位的余数为答案的。
            if(c[m]>='A'&&c[m]<='Z'){
                tmp[i]=c[m]-'A'+10;
                continue;
            }
            if(c[m]>='a'&&c[m]<='z'){
                tmp[i]=c[m]-'a'+36;
                continue;
            }
            else {
                tmp[i]=c[m]-'0';
            }
        }
        for(k=0;len;){
            for(int i=len-1;i;i--)                 //这就是短除法。
            {
                tmp[i-1]+=tmp[i]%b*a;
                tmp[i]/=b;
            }
            ans[k++]=tmp[0]%b;
            tmp[0]/=b;
            for(;len>0&&!tmp[len-1];len--);
        }
        printf("%d %s
%d ",a,c,b);
        for(int i=k-1;i>=0;i--)    //输出答案，逆序输出
        {
            if(ans[i]>=10&&ans[i]<36){
                printf("%c",ans[i]-10+'A');
                continue;
                }
            if(ans[i]>=36){
                printf("%c",ans[i]-36+'a');
            }
            else printf("%d",ans[i]);
        }
        printf("

");
    }
    return 0;
}