백준 31247번 - 2024는 무엇이 특별할까? (JAVA)

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

 

어떤 수 x의 짝수 약수의 개수를 a라고하고, 홀수 약수의 개수를 b라고 할 때,

a = K * b를 만족하는 x를 K-특별한 수라고 한다.

 

K 가 0일 경우, 모든 홀수가 K- 특별 수가 된다.

 

K = 1일 경우, 짝수 개수와 홀수 개수가 같은, 즉 홀수 약수로만 구성된 수(홀수)에 모두 2를 곱하면 된다.

 

K = 2일 경우, 홀수 약수 개수의 2배가 짝수 약수 개수여야한다, 홀수 약수로만 구성된 수에 2를 곱하고, 또 그 곱한 값에 2를 곱한다.

 

이때, 어떤 수 x는 가장 큰 약수와 같다.

 

따라서, 어떤 홀수 x에 2^K을 곱한 값은 K - 특별 수가 됨을 알 수 있다.

Y 이하의 2^K의 홀수 배수의 개수를 구하기 위해서는, 먼저 홀짝을 가리지 않고 2^K의 모든 배수의 개수를 구한다.

이때, 2^K의 홀수 배수만 거르기 위해서는, Y / 2^K 의 값이 짝수일 경우, 2로 나누고, 홀수일 경우 1을 빼고 2를 나눈 값을 빼주면된다. (항상 1부터 시작하기 때문이다)

 

 

 

*** 주의 ***

 

Math.pow() 의 리턴 값을 바로 정수형으로 캐스팅해서 풀다가,

 

오차가 발생한다는 부분을 간과하여, 몇 시간을 날려먹었다.. 다른 분은 절대 같은 실수를 하지 않기를 바란다.

 

 

 

 

- 정답 코드

import java.io.*;
import java.util.*;

class Main {
    static long[] pow;
    public static void main(String[] args) throws IOException {
        pow = new long[64];
        pow[0] = 1;
        for (int i = 1; i <= 63; i++) {
            pow[i] = pow[i - 1] * 2;
        }

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        StringBuilder result = new StringBuilder();
        int T = Integer.parseInt(bf.readLine());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(bf.readLine());

            long N = Long.parseLong(st.nextToken());
            long K = Long.parseLong(st.nextToken());

            if (K >= 63)
                result.append(0).append("\n");
            else {
                int tmp = (int) K;
                long ans = (N / pow[tmp]);
                if (ans % 2 == 0)
                    result.append(ans / 2).append('\n');
                else
                    result.append(ans - (ans - 1) / 2).append('\n');


            }
        }
        System.out.println(result);
    }
}