ABC 105 | C - Base -2 Number

問題

https://atcoder.jp/contests/abc105/tasks/abc105_c

解法

$-2$進数が表現できる範囲の数は以下のようになる。

$N$を$S_i$で表すと以下である。

よって$N$を$-2$で0になるまであまりをひきながら割っていけばいい。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  if (n == 0) {
    cout << 0 << endl;
    return 0;
  }
  string ans = "";
  while (n != 0) {
    if (n % 2 != 0) {
      n--;
      ans = "1" + ans;
    } else {
      ans = "0" + ans;
    }
    n /= -2;
  }

  cout << ans << endl;
}

参考

https://atcoder.jp/contests/abc105/editorial