简介

本文是从零开始刷力扣系列的第三部分，欢迎大家一起讨论、吐槽、提出宝贵意见。在看本篇题解之前，小伙伴们也可以先看看我对刷题顺序的建议。有没有人一起从零开始刷力扣

进制的理解

同样是765432，在不同进制下，代表不同的数：在10进制数下，代表$7\ast 10^5+6\ast 10^4+5\ast 10^3+4\ast 10^2+3\ast 10^1+2\ast 10^0=765432$。在8进制数下，代表$7\ast 8^5+6\ast 8^4+5\ast 8^3+4\ast 8^2+3\ast 8^1+2\ast 8^0=256974$。在16进制数下，代表$7\ast 16^5+6\ast 16^4+5\ast 16^3+4\ast 16^2+3\ast 16^1+2\ast 16^0=7754802$。

k进制转换成十进制

k进制转换为十进制的办法比较简单，直接对应位乘上对应的系数就可以了。参考代码如下：

int ret = 0;
for (int i = 0; i < s.length(); i++) {
    ret = ret * k + s[i] - '0';
}
return ret;

十进制转换成k进制

先思考一个问题，怎么提取k进制的第i位？我们以一个例子来分析这个问题。提取十进制$(765432{)}_{10}$的第2位(从右往左，下标从0开始计算，即百位)。显然，这个数等于$765432/10/10\%10=765432/(10^2)\%10=4$。同样，$(765432{)}_8$的第3位是$256974/（8^2）\%8$。所以，将十进制转换位k进制，我们可以从$k^0$开始枚举系数，对$k^i$求模，得到$m_i$即为第$i$位数。k进制正整数字符串转为十进制的代码如下：

if (num == 0) {
    return "0";
}
string ret;
while (num > 0) {
    ret = (char)(num % k + '0') + ret;
    num /= k;
}
return ret;

数字的位操作

在这部分题目中，关键考察进制转换，进制的理解，以及对数字位的提取与分析。

对应题目及题解

简单数学题

这部分题目主要考察对数字的敏感度，以及找规律的能力。

对应题目及题解

快速幂

模的性质

对于求模，有以下的性质：

1. $(a+b+c)\%d=((a\%d+b)\%d+c)\%d$
2. $(a\ast b\ast c)\%d=((a\%d\ast b)\%d\ast c)\%d$

快速幂

快速幂用于求$x=a^n$，一般$n$是很大的数。那么，我们可以将$n$分解成$k$进制求和的形式(一般k为2)即$n={\sum }_i{k}^i$。由于$a^{b+c}=a^b\ast a^c$，所以$x={\prod }_i{a}^{k^i}$。之后，我们将所有的$a^{k^i}$累乘到结果中即可。若要求模，则应用上述的性质2。

对应题目及题解