17 난닝 지역 경기 F - 더 초센 원 [법칙]

제목 링크
https://nanti.jisuanke.com/t/19972
제목
n 을 주고 n 개의 숫자를 1 -> n 으로 표시합니다
순서대로 배열해서 매번 기수의 수를 뽑아내고 마지막에 남은 숫자의 번호를 구하세요.
생각
과정을 시뮬레이션하면 규칙을 발견할 수 있어요.
예: n = 9
그렇다면
1 2 3 4 5 6 7 8 9
빼면 바로.
2 4 6 8
우리는 이 네 개의 숫자를/2로 할 수 있다
바로
1 2 3 4
그리고 사실 귀속의 하위 문제인 걸 알 수 있어요. 이게 n=4의 경우예요.
뽑으면 남는 걸 발견할 수 있어요.
2, 4 하면 나머지.
1 2
귀속의 하위 문제이기도 하다
마지막 그 숫자는 2입니다.
법칙이 1 -> n이라는 숫자 중에서 2를 가장 많이 제거할 수 있는 숫자가 정답이라는 걸 알 수 있어요.
분명히 <= n의 2의 멱 횟수이다
AC 코드

import java.math.BigInteger;
import java.util.*;

public class Main 
{
    public static void main(String[] args) 
    {
        Scanner cin = new Scanner(System.in);
        int t = cin.nextInt();
        while (t-- != 0)
        {
            BigInteger n = cin.nextBigInteger();
            BigInteger ans = new BigInteger("2");
            System.out.println(ans = ans.pow(n.bitLength() - 1));
        }
    }
}