[백준 Java] 1407번 2로 몇 번 나누어질까(정수론)

💡문제

[Gold IV] 2로 몇 번 나누어질까 - 1407

문제 링크

성능 요약

메모리: 11552 KB, 시간: 76 ms

---

🌟풀이

범위가 무려 1≤A≤B≤$10^{15}$ 로 엄청나다.
그래서 A ~ B 까지 순회하면서 더할 수는 없다.

1 ~ n까지 소수 x의 배수의 개수를 구하는 방식을 이용하였다.

1 ~ n까지 수들은 소수 x로 몇번 나누어 떨어질까 ?

1부터 20까지 순회하며 각 수를 소인수분해 했을때 2가 몇 번씩 들어가는지 적어보았다.

이를 2가 들어간 횟수만큼 동그라미로 표현하게 되면 아래 사진과 같이 표시되며 오른쪽과 같은 의미를 가질 수 있다.

위를 참고하여

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

2로 나누어 지지 않는 수(홀수)는 $2^0 = 1$인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.

그러면 여기서 홀수의 개수는 어떻게 구할까 ?
-> ceil(20/2) = 10

---

| 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 |

4로 나누어 지지 않는 수는 $2^1 = 2$인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.
그러면 여기서 4로 나누어 지지 않는 수의 개수는 어떻게 구할까 ?
-> ceil(10/2) = 5

---

| 4 | 8 | 12 | 16 | 20 |

8로 나누어 지지 않는 수는 $2^2 = 4$인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.
그러면 여기서 8로 나누어 지지 않는 수의 개수는 어떻게 구할까 ?
-> ceil(5/2) = 3 (이런 경우 때문에 올림을 해야한다)

---

| 8 | 16 |

16로 나누어 지지 않는 수는 $2^3 = 8$인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.
그러면 여기서 8로 나누어 지지 않는 수의 개수는 어떻게 구할까 ?
-> ceil(2/2) = 1

---

| 16 |

32로 나누어 지지 않는 수는 $2^4 = 16$인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.
그러면 여기서 16로 나누어 지지 않는 수의 개수는 어떻게 구할까 ?
-> ceil(1/2) = 1

---

이렇게 $2^0$ ~ $2^4$ 들을 가장 큰 약수로 가지는 수들의 개수를 각각 알아봤다.
이 수를 다 더하면

1*10 + 2*5 + 4*3 + 8*1 + 16*1 = 56
이며 이 숫자는 1 ~ 20까지의 2의 거듭제곱큰약수들의 합이 된다.

이를 이용하여 1 ~ B 에서 1 ~ A-1을 빼주면 A~B까지의 합을 구할 수 있다.
f(B) - f(A-1)

---

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_1407 {
    static long A;
    static long B;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = Long.parseLong(st.nextToken());
        B = Long.parseLong(st.nextToken());

        // A부터 B까지의 수 중 2의 거듭제곱 꼴이면서 가장 큰 약수를 찾아 더하여 출력
        System.out.println(twoCount(B) - twoCount(A - 1));
    }

    /**
     * A부터 B까지의 수 중 2의 거듭제곱 꼴이면서 가장 큰 약수를 찾아 더하는 메서드
     *
     * @param n 약수를 찾을 대상 숫자
     * @return 2의 거듭제곱 꼴이면서 가장 큰 약수를 찾아 더한 결과
     */
    private static long twoCount(long n) {
        long result = 0;
        long divisor = 1;

        // 2의 거듭제곱 꼴이면서 가장 큰 약수를 찾기 위한 반복문
        while (n > 0) {
            // 현재의 divisor로 나누어지지 않는 숫자의 가장 큰 약수를 찾아 더함
            long indivisibleNumberCnt = n / divisor;

            // 결과에 현재 divisor와 가장 큰 약수를 곱하여 누적
            result += divisor * indivisibleNumberCnt;

            // 다음 거듭제곱으로 이동
            divisor *= 2;
        }
        return result;
    }
}

[[ 참고 ] (https://velog.io/@bgg01578/%EB%B0%B1%EC%A4%80-1407-2%EB%A1%9C-%EB%AA%87-%EB%B2%88-%EB%82%98%EB%88%84%EC%96%B4%EC%A7%88%EA%B9%8C)]