这类问题的相同之处在于，数的大小超出了原生数据类型所能表示的范围。如果用Python或者Java，就不必再看下去了。。。。。。

1. 大数的模幂运算

给定x和y，求x的y次幂模k的余数

unsigned int quick_power_mod(unsigned int x, unsigned int y, unsigned int k) { unsigned int res = 1; x %= k; while(y != 0) { if(y & 1) { res = (res * x) % k; } y >>= 1; x = (x * x) % k; } return res; } 这种做法的道理如下，指数y的二进制表示为： $y = a_{0} cdot 2^{0} + a_{1} cdot 2^{1} + a_{2} cdot 2^{2} + cdots + a_{n} cdot 2^{n}, a_{i} in {0, 1}$ 那么 $x^{y} = x^{a_{0} cdot 2^{0} + a_{1} cdot 2^{1} + a_{2} cdot 2^{2} + cdots + a_{n} cdot 2^{n}} = x^{a_{0} cdot 2^{0}} cdot x^{a_{1} cdot 2^{1}} cdot x^{a_{2} cdot 2^{2}} cdot cdots cdot x^{a_{n} cdot 2^{n}} , a_{i} in {0, 1}$ 又因为模运算有如下性质 $(a cdot b)mod c = ((a mod c)(b mod c)) mod c$ 于是我们有 $x^{y} mod k = ((x^{a_{0} cdot 2^{0}} mod k) cdot (x^{a_{1} cdot 2^{1}} mod k) cdot (x^{a_{2} cdot 2^{2}} mod k) cdot cdots cdot (x^{a_{n} cdot 2^{n}} mod k)) mod k, a_{i} in {0, 1}$ 该算法即在按照上式从左到右一项一项的计算。体现为，遍历y的每一个二进制位，如果该位为1，将当前的计算结果乘以当前x的值并求余，如果该位为0，则不乘或者说乘以1；每遍历y的一位，将x做一次平方，对应着上式中依次乘2的x的指数。

2. 大数的进制转换

给定a进制的数x（字符串形式），转换为b进制的数y

// big-endian for input // small-endian for output unsigned int convert_base(std::vector<unsigned int> &from_num, std::vector<unsigned int> &to_num, unsigned int from_base, unsigned int to_base) { for(int i = 0; i < from_num.size(); ) { int carry = 0; for(int j = i; j < from_num.size(); j++) { int tmp = (from_num[j] + carry * from_base) % to_base; from_num[j] = (from_num[j] + carry * from_base) / to_base; carry = tmp; } to_num.push_back(carry); while(from_num[i] == 0) { i++; } } } 此处使用的是除k取余法，输入的vector也被改变了，用来存储每步计算的商。