問題一覧 > 通常問題

No.3547 Rurumaru Function Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : ルク / テスター : 👑 loop0919 ぽえ
ProblemId : 13327 / yukicoder contest 500 (順位表) / 自分の提出
問題文最終更新日: 2026-04-22 21:41:51
yukicoder contest 500の他の問題:

問題文

非負整数 $x,y$ に対し、 $f(x,y)$ を以下のように定義された非負整数とします。
  • $f(x,y)$ を二進表記したときの $2^i(i \ge 0)$ の位の値は、
    • $i$ が偶数ならば、$x$ の $2^i$ の位の値と $y$ の $2^i$ の位の値の論理積(AND)を取った値。
    • $i$ が奇数ならば、$x$ の $2^i$ の位の値と $y$ の $2^i$ の位の値の論理和(OR)を取った値。
例えば、$f(2,14)=10$ です。(二進表記にすると$f(0010_{(2)},1110_{(2)})=1010_{(2)}$ となります。)

非負整数 $N,M$ が与えられます。$f(x, N)=M$ となるような最小の非負整数 $x$ を求めてください。
存在しなければ -1 を出力してください。

制約

  • $0 \le N \lt 2^{30}$
  • $0 \le M \lt 2^{30}$
  • 入力はすべて整数である

入力

$N\ M$

出力

答えを出力せよ。

サンプル

サンプル1
入力
31 14
出力
4
$f(4, 31) = f(00100_{(2)}, 11111_{(2)})=01110_{(2)}=14$ が成り立ち、$4$ 未満のこれを満たす $x$ は存在しないため $4$ を出力してください。
サンプル2
入力
314 159
出力
-1

これを満たす非負整数 $x$ が存在しないことが証明できます。
よって -1 を出力してください。

サンプル3
入力
1073741823 1073741823
出力
357913941

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。