0x01 特殊：base=-2
0x02 前置知识：c++ %规则
我们需要知道，在 \(C\)++ 中，余数的符号取决于被除数，也即，a%b=c 中 \(c\) 的符号取决于 \(a\) 的符号，即，\(a\) 是什么符号，\(c\) 就是什么符号，与 \(b\) 的符号无关。
int a[4] = {11, 11, -11, -11};
int b[4] = {2, -2, 2, -2};
for(int i = 0; i < 4; i ++ )
cout << a[i] / b[i] << "..." << a[i] % b[i] << endl;
输出结果为：
5...1
-5...1
-5...-1
5...-1
另外，a/b=c 中 \(c\) 的符号是显而易见的，如果 \(a\) 和 \(b\) 同符号，\(c\) 就是正号，反之，如果 \(a\) 和 \(b\) 异号，\(c\) 就是负号。
知道了上述规则，a/b=c..d 的 \(c\) 和 \(d\) 的值我们就可以自己求解了。
0x03 前置知识：取整规则
\(C\)++ 和 \(Java\) 是向 \(0\) 取整，\(Python\) 是下取整
0x04 十进制转其他进制 -- 辗转相除法
如果将一个 \(10\) 进制转换为一个 \(2,3,4,....n\)（正数） 进制，是很容易的，我们直接辗转相处然后对字符串 \(reverse\) 就行了。当然，如果数字不够用，还需要用到 \(a,b,c..\)
但是今天做到 0x01 这道题时，着实让我烧脑筋了，因为我想知道一种通用的解法，不仅仅局限于进制为 \(-2\) 的情况，对于 \(-3,-4,-5\) 甚至于 \(2,3,4\) 都可以通用的解决。
其实，当进制为负数时主要有一个问题：那就是，辗转相除时，余数可能为负数，此时该怎么办呢？
首先，余数为负数说明被除数肯定是个负数（\(0x02\)）。
并且被除数（也就是 \(base\)）也肯定是个负数，因为我们规定输入的十进制数都是正数，而这里被除数（十进制数）成了负数，说明此时除数肯定是负数。
好了，现在回归正题，我们肯定不能让余数为负数啊，所以我们需要把它转换为非负数。
直接告诉你方法：如果余数为负数，就加上进制的绝对值。
为什么这么做是正确的？因为我们可以很自然的修改商。
例如：十进制数为 \(a=-11\)，进制为 \(b=-2\)，商为 \(c\)，余数为 \(d\)。
-11/-2=5...-1，因此我们需要让 \(d=-1+abs(-2)=1\)，但是修改了 \(-1\)，\(c*b+d==a\) 的等价关系就不成立了。
因此，我们还需要修改商，这里，我们只需要让商直接 \(+1\) 就好了。
因为让余数加上进制的绝对值就相当于让余数减去进制（前面证明了，进制一定是负数），所以我们需要让商 \(+1\)，相当于把减去的进制加上了。
这样：(c+1)*b+(d-b)==c*b+d==a 依然成立。
如果我们不是让余数加上进制的绝对值，而是加上了一个其他的数，此时我们仍然需要通过改动商来维护等价关系（不可能修改进制，修改除数没意义）。
但是此时，商可能变成一个浮点数，例如，余数加上了 \(k\)，那么我们需要让 (c+q)*b+(d+k)==c*b+d 成立。
就需要让 \(q=-k/b\)，\(q\) 未必是个整数。
0x05 通解：abs(bsae)<10
当 \(base>=10\) 时需要用到 \(a,b,c,....\)，这应该不会考到，也不需要用，\(16\) 进制就很好了。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cassert>
#include <cmath>
using namespace std;
const int N = 1024 * 1024;
// 将正整数n转换为base进制并输出结果
// abs(base) < 10 && base != 0
string toBaseStr(int n, int base);
// 测试程序
void test();
string toBaseStr(int n, int base);
int main()
{
test();
return 0;
}
string toBaseStr(int n, int base)
{
assert(base);
if(n == 0) return "0";
string res("");
while(n)
{
int c = n % base;
n /= base;
if(c < 0) c -= base, n ++ ;
res += to_string(c);
}
reverse(res.begin(), res.end());
return res;
}
static void doTestBase(int base)
{
int debuger = 0;
for(int i = 0; i < N; i ++ )
{
string s = toBaseStr(i, base);
string t = s;
int n = s.size();
int test = 0;
reverse(t.begin(), t.end());
for(int j = 0; j < n; j ++ )
if(t[j] != '0')
test += (t[j] - '0') * pow(base, j);
if(test != i)
cout << "[Wrong" << ++ debuger << "]: " << i << "->" << s << " is " << test << endl;
// else
// cout << "[Accpet]: " << i << "->" << s << " is " << test << endl;
}
if(!debuger)
cout << "[Accept] base = " << base << endl;
}
void test()
{
clock_t start = clock();
for(int i = 2; i < 10; i ++ )
{
doTestBase(i);
doTestBase(-i);
}
printf("CPU Time = %.2lfs\n", (clock() - start) * 1.0 / CLOCKS_PER_SEC);
}