はじめに
皆さんこんにちは！ 競プロの問題の理解を深めるために解説記事を書いていこうと思います！今回は ABC234 C です！
気に入っていただけたらLGTMして頂けるとうれしいです！
わからないことなどあれば下のコメントやTwitterからお願いいたします!
C - Happy New Year!
問題概要
10進法にしたときに0, 2で表される正整数のうち$K$番目の数を求めよ．
制約
$1 \leq K \leq 10^{18} $
考察
ポイント
2進数に変換しよう
解説
0,2からなる正整数を小さいほうから並べてみると
1 : 2 -> 1
2 : 20 -> 10
3 : 22 -> 11
4 : 200 -> 100
5 : 202 -> 101
6 : 220 -> 110
7 : 222 -> 111
8 : 2000 -> 1000
となります．
これの2を1に置き換えると ->のとおり10進数を2進数で変換したものと同じであることがわかります．
これより$K$を2進数に変換すれば答えがわかります．
実装
2進数に変換するのはwhile文で$K$を2で割っていきます．出力は文字列で2で割り切れたら2を，割り切れなかったら0を文字列の前に足していきます．
2進数の変換を理論的に述べているサイトを紹介します．
正解コード
# include <bits/stdc++.h>
using namespace std;
int main()
{
//入力
long long K;
cin >> K;
//解答は文字列で宣言
string ans = "";
//2進数に変換
while (K > 0)
{
int a = K % 2;
K /= 2;
ans = (char)('0' + 2 * a) + ans;
}
//出力
cout << ans << endl;
}