[c++ 백준] (24500번) blobblush

문제

귀여운 아기 주환이에게는 1$1$부터 N$N$까지의 양의 정수가 적힌 숫자 카드가 있다.

주환이는 오늘이 자신과 가장 친한 아기 블롭의 생일이라는 사실을 알고, 선물로 K$K$장의 카드를 주었다.

주환이는 카드를 다음 조건에 맞게 뽑았다.

• 뽑은 카드들에 적힌 수를 모두 ⊕한 값이 최대가 되어야 한다. ⊕는 배타적 논리합(xor)을 의미한다.
• 첫 번째 조건에 맞게 카드를 뽑는 방법이 여러 가지인 경우, 카드를 최대한 적게 뽑아야 한다.
• 두 번째 조건에 맞게 카드를 뽑는 방법이 여러 가지인 경우, 사전 순으로 가장 앞서도록 뽑아야 한다.

 K$K$와 고른 카드에 적힌 각 수를 구하자.

입력

첫째 줄에 N$N$이 주어진다.

출력

첫째 줄에 K$K$를 출력한다. K$K$는 N$N$ 이하인 양의 정수이다.

둘째 줄부터 조건을 만족하는 K$K$개의 카드에 적힌 양의 정수를 한 줄에 하나씩 오름차순으로 출력한다.

가능한 답이 여러 경우라면, 사전 순으로 가장 앞서는 것을 출력한다.

제한

•  1≤N≤1018$1 \leq N \leq 10^{18}$ 

https://www.acmicpc.net/problem/24500

24500번: blobblush

---

풀이과정

1. 비트 연산을 이용한 수학 문제입니다.

2. 범위는 1~10의 18승까지 이기 때문에 long long 자료형을 사용했습니다.

3. 문제에서 카드를 뽑고 xor 시 가장 큰 수가 되게 하는 것 이기 때문에 모든 비트가 1이 되게 하는 수를 찾아야 합니다.

먼저

	long long  M = 1;
	while (M < N) M = M * 2 + 1;

를 통해 모든 비트가 1인 N보다 크거나 같은 수를 찾습니다.

그리고 N과 M 이 같으면 모든 비트가 1인 수 이므로 출력

아니면 N에 모든 비트를 1로 만들어 주는 수를 찾습니다. xor 연산자를 통해 수를 찾을 수 있습니다.

ex)

N = 7 일 경우 카드 1개 출력 N 만 출력

N	0	0	0	0	0	1	1	1	7
M	0	0	0	0	0	1	1	1	7
N	0	0	0	0	0	1	1	1	7

N = 8 일 경우 카드 2개 출력 최대 15를 만들 수 있다.

N	0	0	0	0	1	0	0	0	8
M	0	0	0	0	1	1	1	1	15
N ^ M	0	0	0	0	0	1	1	1	7
N	0	0	0	0	1	0	0	0	8

---

코드

#include<iostream>
#define endl "\n"
using namespace std;

void Answer()
{
	long long N; cin >> N;
	long long  M = 1;
	while (M < N) M = M * 2 + 1;
	if (M == N) cout << 1 << endl << N;
	else cout << 2 << endl << (M ^ N) << endl << N;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	Answer();
	return 0;
}