[yukicoder] No. 1298 OR XOR

2020年12月12日

問題

方針

ビット演算を題材にした問題は、ビット毎に考えることがあります。自然数 \( 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;
}