🔗 UVA-11121 Base -2

tags: `模擬(Simulation)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意：

如同十進位(base 10) 和二進位(base 2) ，在負二進位(base -2) 中，一個整數 $n$ 可以表示成 $n = b_0 + b_1(-2) + b_2(-2)^2 + b_3(-2)^3 + \cdots$ ，其中 $b_i$ 必須為 $0$ 和 $1$ 。
每個整數都有一個唯一的負二進位表示，不需要負號。輸入一個十進位整數 $n$ ，輸出其負二進位表示。

思路：模擬(Simulation) + 進制轉換

和一般的進位轉換類似，可以用除法和取餘數的方式來轉換。不過在負二進位表示中只能有 $0$ 和 $1$ 兩個數字，而除以 $-2$ 會餘數為負數的情況，因此我們可以在餘數為負數時將商加 $1$ ，餘數加 $2$ 來保證餘數為正數。
隨後將餘數加入答案中，並將商更新為新的數字，重複上述步驟直到商為 $0$ ，最後將答案反轉即可。
舉例來說，測試資料中 $7$ $7$ 的負二進位表示為 $11011$ $11011$ 可以這樣求出：
- $7 \div -2 = -4 ... -1 \Rightarrow -3 ... 1$
- $-3 \div -2 = 1 ... -1 \Rightarrow 2 ... 1$
- $2 \div -2 = -1 ... 0$
- $-1 \div -2 = 0 ... -1 \Rightarrow 1 ... 1$
- $1 \div -2 = -1 ... -1 \Rightarrow 0 ... 1$
時間複雜度為： $O(\log n)$ 。
空間複雜度為： $O(\log n)$ 。

T = int(input())

for tc in range(1, T+1):
    n = int(input())
    ans = ""
    while n:
        q, r = divmod(n, -2)
        if r < 0:
            q += 1
            r += 2
        ans += str(r)
        n = q
    print(f"Case #{tc}: {ans[::-1] if ans else 0}")

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t, tc=1, n, q, r;
    cin >> t;
    while (t--) {
        cin >> n;
        string ans = "";
        while (n) {
            q = n / -2;
            r = n % -2;
            if (r < 0) {
                q += 1;
                r += 2;
            }
            ans += to_string(r);
            n = q;
        }
        reverse(ans.begin(), ans.end());
        cout << "Case #" << tc++ << ": " << (ans.empty() ? "0" : ans) << endl;
    }
    return 0;
}