Problem Description

As we already know, base64 is a common binary-to-text encoding scheme. Here we define a special series of positional systems that represent numbers using a base (a.k.a. radix) of 2 to 62. The symbols ‘0’ – ‘9’ represent zero to nine, and ‘A’ – ‘Z’ represent ten to thirty-five,and ‘a’ – ‘z’ represent thirty-six to sixty-one. Now you need to convert some integer z in base x into base y.

Input

The input contains three integers x; y (2 ≤ x; y ≤ 62) and z (0 ≤ z < x120), where the integer z is given in base x.

Output

Output the integer z in base x.

Sample Input

16 2 FB

Sample Output

11111011

Analysis of ideas

利用短除法

Accepted code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define cin(a) scanf("%d",&a)
#define ll long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 1100;

int getnum(char ch) //字符转数字
{
    if(ch <= '9') return ch-'0';
    else if(ch <= 'Z') return 10+ch-'A';
    else return 36+ch-'a';
}

char getch(int num) //数字转字符
{
    if(num <= 9) return num+'0';
    else if(num <= 35) return num-10+'A';
    else return num-36+'a';
}

int n,m;
char str1[maxn],str2[maxn];
int t[maxn],ans[maxn];


void solve()
{
    int len = strlen(str1);

    for(int i = 0; i < len; i++)    //先把字符串变成数组,高位->低位
        t[i] = getnum(str1[i]);
    
    int j = 0,k = 0;
    while(j < len)
    {
        for(int i = j; i < len-1; i++)  //除以m,把余数加到下一位
        {
            t[i+1] += t[i] % m * n;
            t[i] /= m;
        }
        
        ans[k++] = t[len-1]%m;      //个位数余m
        t[len-1] /= m;

        while(j < len && !t[j]) j++;    //最高位是0,j++
    }

    for(int i = 0; i < k; i++)  //逆序变成字符串
    {
        str2[i] = getch(ans[k-i-1]);
    }
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t;
    cin(t);
    while(t--)
    {   
        mem(ans,0),mem(str2,0); //wa
        cin>>n>>m;
        cin>>str1;
        solve();
        cout<<n<<' '<<str1<<endl;
        cout<<m<<' '<<str2<<endl<<endl;
    }
    
}