涉及进制转换、高精度整数

例 4.13 进制转换 （九度教程第 62 题）
时间限制： 1 秒 内存限制： 32 兆 特殊判题：否
题目描述：
将 M 进制的数 X 转换为 N 进制的数输出。
输入：
输入的第一行包括两个整数： M 和 N(2<=M,N<=36) 。
下面的一行输入一个数 X，X 是 M 进制的数，现在要求你将 M 进制的数 X
转换成 N 进制的数输出。
输出：
输出 X 的 N 进制表示的数。
样例输入：
16 10
F
样例输出：
15
提示：
输入时字母部分为大写，输出时为小写，并且有大数据。
来源：
2008 年清华大学计算机研究生机试真题
该题初看起来很像一般的进制转换，但提示中明确告知，输入会有较大的数
据，即我们为了完成本例需要的进制转换，需要使用高精度整数。同时，考虑到
进制转换的内容，我们的高精度整数需要进行以下运算：高精度整数与普通整数
的求积，高精度整数之间求和，高精度整数除以普通整数，高精度整数对普通整
数求模等。下面给出本例代码，作为本章最后的总结内容。

#include <stdio.h> 
#include <string.h> 
#define maxDigits 100 
struct bigInteger { //高精度整数结构体
int digit[maxDigits]; 
int size; 
void init() { //初始化
for (int i = 0;i < maxDigits;i ++) digit[i] = 0; 
size = 0; 
} 
void set (int x) { //用一个普通整数初始化高精度整数
init(); 
do { 
digit[size ++] = x % 10000; 
x /= 10000; 
} while(x != 0); 
} 
void output() { //输出
for (int i = size - 1;i >= 0;i --) { 
if (i != size - 1) printf( "%04d" ,digit[i]); 
else printf( "%d" ,digit[i]); 
} 
printf( "\n" ); 
} 
bigInteger operator * ( int x) const { //高精度整数与普通整数的乘积
bigInteger ret; 
ret.init(); 
int carry = 0; 
for (int i = 0;i < size;i ++) { 
int tmp = x * digit[i] + carry; 
carry = tmp / 10000; 
tmp %= 10000; 
ret.digit[ret.size ++] = tmp; 
} 
if (carry != 0) { 
ret.digit[ret.size ++] = carry; 
} 
return ret; 
} 
bigInteger operator + ( const bigInteger &A) const { //高精度整数之间的加法运算
bigInteger ret; 
ret.init(); 
int carry = 0; 
for (int i = 0;i < A.size || i < size;i ++) { 
int tmp = A.digit[i] + digit[i] + carry; 
carry = tmp / 10000; 
tmp %= 10000; 
ret.digit[ret.size ++] = tmp; 
} 
if (carry != 0) { 
ret.digit[ret.size ++] = carry; 
} 
return ret; 
} 
bigInteger operator / (int x) const { //高精度整数除以普通整数
bigInteger ret; //返回的高精度整数
ret.init(); //返回值初始化
int remainder = 0; //余数
for (int i = size - 1;i >= 0;i --) { //从最高位至最低位依次完成计算
int t = (remainder * 10000 + digit[i]) / x; //计算当前位数值加上高位剩余的余数的和对 x求得的商
int r = (remainder * 10000 + digit[i]) % x; //计算当前位数值加上高位剩余的余数的和对 x求模后得的余数
ret.digit[i] = t; //保存本位的值
remainder = r; //保存至本位为止的余数
} 
ret.size = 0; // 返 回 高 精 度 整 数 的 size 初 始 值 为 0, 即 当 所 有 位 数 字 都 为 0 
//时,digit[0]代表数字 0,作为最高有效位 ,高精度整数即为数字 0 
for (int i = 0;i < maxDigits;i ++) { 
if (digit[i] != 0) ret.size = i; 
} //若存在非 0位,确定最高的非 0位,作为最高有效位
ret.size ++; //最高有效位的下一位即为下一个我们不曾使用的 digit数组单元 ,确定为size的值
return ret; //返回
} 
int operator % ( int x) const { //高精度整数对普通整数求余数
int remainder = 0; //余数
for (int i = size - 1;i >= 0;i --) { 
int t = (remainder * 10000 + digit[i]) / x; 
int r = (remainder * 10000 + digit[i]) % x; 
remainder = r; 
} //过程同高精度整数对普通整数求商
return remainder; //返回余数
} 
}a , b , c; 
char str[10000]; 
char ans[10000]; 
int main () { 
int n, m; 
while (scanf ("%d%d" ,&m,&n) != EOF) { 
scanf ("%s" ,str); //输入 m进制数
int L = strlen(str); 
a.set(0); //a初始值为 0,用来保存转换成 10进制的 m进制数
b.set(1); //b 初始值为 1,在m进制向 10进制转换的过程中 ,依次代表每一位的权重
for (int i = L - 1;i >= 0;i --) { //由低位至高位转换 m进制数至相应的 10进制数
int t; 
if (str[i] >= '0' && str[i] <= '9') { 
t = str[i] - '0'; 
} 
else t = str[i] - 'A' + 10; //确定当前位字符代表的数字
a = a + b * t; //累加当前数字乘当前位权重的积
b = b * m; //计算下一位权重
} 
int size = 0; //代表转换为 n进制后的字符个数
do { //对转换后的 10进制数求其 n进制值
int t = a % n; //求余数
if (t >= 10) ans[size ++] = t - 10 + 'a';
else ans[size ++] = t + '0'; //确定当前位字符
a = a / n; //求商
}while(a.digit[0] != 0 || a.size != 1); //当a不为0时重复该过程
for (int i = size - 1;i >= 0;i --) printf( "%c" ,ans[i]); 
printf( "\n" ); //输出
} 
return 0; 
}