POJ 3191 The Moronic Cowmpouter

大きい桁からその桁が必要かを上限下限から判断する方法でやろうとした
が、n進数(n > 1)とほとんど同じやり方でできるみたいなのでそうした
参考: wikipedia:en:Negative_base

ソースコード

vector<int> to_negabase(ll n, int base)
{
    vector<int> res;
    if (n == 0)
    {
	res.push_back(0);
	return res;
    }

    while (n != 0)
    {
	int rem = n % base;
	n /= base;
	if (rem < 0)
	{
	    rem += -base;
	    ++n;
	}
	res.push_back(rem);
    }
    return res;
}
string to_negabase_s(ll n, int base)
{
    vector<int> digits = to_negabase(n, base);
    string res;
    for (int i = digits.size() - 1; i >= 0; --i)
	res += to_s(digits[i]);
    return res;
}
int main()
{
    int n;
    cin >> n;
    cout << to_negabase_s(n, -2) << endl;
}