C :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 2000
char str[LEN], another[LEN];
int  ten[LEN];
int switchToTen(int m);
void switchToAnother(int k, int n);

int main()
{
    int m, n, k;
    while (scanf("%d %d", &m, &n) != EOF)
    {
        scanf("%s", str);
        k = switchToTen(m);
        switchToAnother(k, n);
    }
    return 0;
}

int switchToTen(int m)
{
    int i, j, len, k, c;
    len = strlen(str);
    k = 1;
    memset(ten, 0, sizeof(ten));
    for (i = 0; i < len; i ++) {
        for (j = 0; j < k; j ++)
            ten[j] *= m;
        if (str[i] >= '0' && str[i] <= '9')
            ten[0] += str[i] - '0';
        else if (str[i] >= 'A' && str[i] <= 'Z')
            ten[0] += str[i] - 'A' + 10;
        else if (str[i] >= 'a' && str[i] <= 'z')
            ten[0] += str[i] - 'a' + 10;
        for (j = c = 0; j < k; j ++) {
            ten[j] += c;
            if (ten[j] >= 10) {
                c = ten[j] / 10;
                ten[j] %= 10;
            }else
                c = 0;
        }

        while (c) {
            ten[k ++] = c % 10;
            c /= 10;
        }
    }
    int temp;
    for (i = 0, j = k - 1; i < j; i ++, j --) {
        temp = ten[i];
        ten[i] = ten[j];
        ten[j] = temp;
    }
    return k;
}

void switchToAnother(int k, int n)
{
    int sum, i, r, t, d;

    sum = 1;
    r = 0;
    memset(another, 0, sizeof(another));

    while (sum) {
        sum = 0;

        for (i = 0; i < k; i ++) {
            d = ten[i] / n;
            sum += d;

            if (i == k - 1) {
                t = ten[i] % n;
                if (t >= 0 && t <= 9)
                    another[r] = t + '0';
                else
                    another[r] = t - 10 + 'a';
                r ++;
            }else
                ten[i + 1] += ten[i] % n * 10;
            ten[i] = d;
        }
    }
    for (i = r - 1; i >= 0; i --)
        printf("%c", another[i]);
    printf("\n");
}

C++ :

#include<stdio.h>
#include<string.h>

char result[1000];

void base_convert(char num[],int s,int e)
{
	int i,flag,k,j,a[1000],b[1000];
	for(i=0;i<strlen(num);i++)
	{
		if(num[i]>='A'&&num[i]<='Z')
			a[i]=num[i]-55;
		else
			a[i]=num[i]-48;
	}
	k=0;
	while(1)
	{
		for(i=0;i<strlen(num);i++)
		{
			if(a[i]!=0&&i<strlen(num)-1)
			{
				a[i+1]+=(a[i]%e)*s;
				a[i]/=e;
			}
			if(i==strlen(num)-1)
			{
				b[k++]=a[i]%e;
				a[i]/=e;
			}
		}
		flag=0;
		for(i=0;i<strlen(num);i++)
			if(a[i]!=0)
				flag=1;
		if(!flag)
			break;
	}
	for(j=0,i=k-1;i>=0;i--)
	{
		if(b[i]>=10&&b[i]<=35)
			result[j++]=b[i]+87;
		else
			result[j++]=b[i]+48;
	}
	result[j]='\0';
}

int main()
{
	int m,n;
	char x[1000];
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		scanf("%s",x);
		base_convert(x,m,n);
		puts(result);
	}
	return 0;
}