[BOJ] 백준 15917 노솔브 방지문제야!!

문제 링크

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

어떤 수 a가 2의 거듭제곱꼴인지 판별하면 된다.

쿼리의 수 Q가 $1 \leq Q \leq 1,000,000$이므로 단순히 a의 비트를 순회하며 1이 하나인지 확인해도 $O(32Q)$이므로 충분하다.

좀 더 효율적으로 하고싶다면 $a\ \&\ (a - 1)$이 0인지 확인하자.

모든 양수 a에 대해 a가 2의 거듭제곱꼴이라면 위의 값이 0이 나온다.

글을 쓰면서 문제를 다시 확인했는데 힌트 부분에 이미 답이 나와있었다... 닉값하는 문제;;

정답 코드

	#include <iostream>
	using namespace std;
	int m;
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> m;
	while (m--) {
	int a;
	cin >> a;
	if ((a & (a - 1))) cout << 0 << '\n';
	else cout << 1 << '\n';
	}
	}

view raw 15917.cpp hosted with ❤ by GitHub

질문, 피드백 환영합니다.