No.3276 Make Smaller Popcount
タグ : / 解いたユーザー数 58
作問者 :
yu23578
/ テスター :
👑 
p-adic
問題文
正整数 $N$ が与えられるので、$\mathrm{popcount}(N) > \mathrm{popcount}(N+x)$
を満たす正整数 $x$ が存在するか判定し、存在するならばその最小値を解答してください。
$T$個のテストケースが与えられるので、それぞれについて解いてください。
$\mathrm{popcount}$ とは？
$\mathrm{popcount}(x)$ で、 $x$ を二進数表記した時に登場する $1$ の数を表します。 例えば、$13=1101_{(2)}$ なので、$\mathrm{popcount}(13) = 3$ となります。制約
・$1 \le T \le 2 \times 10^5$
・$1 \le N < 2^{30}$
・入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。$T$ここで、 $testcase_i$ は $i$ 番目のテストケースの情報を表し、次の形式で与えられます。
$testcase_1$
$testcase_2$
$testcase_3$
$\vdots$
$testcase_T$
$N$
出力
$T$ 行出力してください。 $i$ 行目には $i$ 番目のテストケースについて、条件を満たすような $x$ が存在するならばその最小値を、存在しないならば-1を出力してください。
サンプル
サンプル1
入力
3
5
7
12
出力
3
1
4
1つ目のテストケースについて、
$x=1$ のとき、 $\mathrm{popcount}(N) = 2 \le \mathrm{popcount}(N+x) = 2$ より不適
$x=2$ のとき、 $\mathrm{popcount}(N) = 2 \le \mathrm{popcount}(N+x) = 3$ より不適
$x=3$ のとき、 $\mathrm{popcount}(N) = 2 > \mathrm{popcount}(N+x) = 1$
よって $x = 3$ を出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。