进制转换，base可能为负数

0x01 特殊：base=-2

LeetCode

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);
}

0x06 参考

ref here