[yukicoder] No. 1298 OR XOR
問題
方針
ビット演算を題材にした問題は、ビット毎に考えることがあります。自然数 \( N \) を \( 2 \) 進数で
\[ N= n_1n_2 \cdots n_{k}\]
と表します。
同様に、\( A, B, C \) についても \( 2 \) 進数で表したとき、\( n_i = 0 \) ならば、
\[ a_i = 0 \wedge b_i = 0 \wedge c_i – 0\]
となります。このとき、排他的論理和も \( 0 \) となります。\( n_i = 1 \) ならば、
\[ (a_i, b_i, c_i) = (0, 1, 1), (0, 1, 0), (0, 0, 1) \]
となります。このとき、排他的論理和は \( 0 \) となります。したがって、\( N = 2^j \) を満たすような \( j \) が存在する場合、題意を満たす \( A, B, C \) は存在しません。そうではないとき、\( A = N \) とし、\( n_i = 1\) を満たす \( i \) を \( 1 \) つ選び、\( B = N – 2^i \wedge C = 2^i\) とすればよいです。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N; cin >> N; int A = N; int B = N; int C = N; for (int i = 0; i < 31; i++) { if ((1<<i) == N) { cout << "-1 -1 -1\n"; return 0; } if (((1<<i) & N) != 0) { B = N - (1<<i); C = (1<<i); } } cout << A << " " << B << " " << C << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません