1407 - 2로 몇 번 나누어질까
본문
자연수 $N$이 주어지면, 자연수를 유지하면서 $N$을 $2$로 몇 번까지 나눌 수 있는지를 생각해 볼 수 있다. 즉, $N$의 모든 약수 중 $2$의 거듭제곱 꼴이면서 가장 큰 약수를 생각하는 것이다. 예를 들어 $15$의 경우는 $2$로 한 번도 나눌 수 없으므로 $2^0 = 1$이 해당되고, $40$의 경우는 $2$로 세 번까지 나눌 수 있으므로 $2^3 = 8$이 해당된다. 이러한 약수를 함수값으로 가지는 함수 $f(x)$를 정의하자. 즉, $f(15) = 1$이고, $f(40) = 8$이다.
두 자연수 $A, B$($A \leq B$)가 주어지면, $A$ 이상 $B$ 이하의 모든 자연수에 대해서, 그 자연수의 모든 약수 중 $2$의 거듭제곱 꼴이면서 가장 큰 약수들의 총 합을 구하는 프로그램을 작성하시오. 즉 아래와 같은 수식의 값을 구해야 한다. \(f(A) + f(A+1) + ... + f(B-1) + f(B)\)
입력
첫째 줄에 자연수 $A$와 $B$가 빈 칸을 사이에 두고 주어진다. ($1 \leq A \leq B \leq 10^{15}$)
출력
첫째 줄에 구하고자 하는 수를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
풀이
생각보다 풀이 과정이 단순하다. 비슷한 문제로 백준 1676번 문제가 있으니 한번쯤 고민해보도록 하자.
문제를 푸는 핵심은, $A$부터 $B$까지의 함수 $f(x)$를 모두 일일히 계산하는 것이 아니라는 것을 알아차리는 것이다. 수의 범위가 최대 $10^{15}$이므로, 애초에 모든 값을 계산한다는 것 자체가 시간에 들지 못한다. 즉 $f(x)$를 계산하지 말고, 특정 기준값 $z$에 대해 $S(x) = \sum_{i=z}^{x}f(i)$를 계산할 수 있으면, $f(A) + f(A+1) + … + f(B-1) + f(B) = S(B) - S(A-1)$로 계산할 수 있다.
문제는 $S(x)$는 어떻게 계산할 수 있을까 하는 것이다. 기준인 $z$의 경우, 가능한 모든 수들보다 작거나 같아야 하므로, 문제에서 가능한 값들 중 최솟값인 $1$로 선택하는 것이 좋다. 그렇다면 $S(x)$를 구하는 방법은 어떻게 될까? 이건 예시를 통해 생각해보자.
| 수 | $2^d$ |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 1 |
| 4 | 4 |
| 5 | 1 |
| 6 | 2 |
| 7 | 1 |
| 8 | 8 |
| 9 | 1 |
| 10 | 2 |
| 11 | 1 |
| 12 | 4 |
| 13 | 1 |
| 14 | 2 |
| 15 | 1 |
| 16 | 16 |
| 17 | 1 |
| 18 | 2 |
| 19 | 1 |
| 20 | 4 |
| 21 | 1 |
| 22 | 2 |
| 23 | 1 |
| 24 | 8 |
| 25 | 1 |
| 26 | 2 |
| 27 | 1 |
| 28 | 4 |
| 29 | 1 |
| 30 | 2 |
| 31 | 1 |
| 32 | 32 |
| 33 | 1 |
| 34 | 2 |
| 35 | 1 |
| 36 | 4 |
| 37 | 1 |
| 38 | 2 |
| 39 | 1 |
| 40 | 8 |
$S(40)$이라면 위의 수를 모두 더한 값이 될 것이다. 여기서 우리가 알 수 있는 점들을 찾아보자. 번뜩이는 아이디어를 찾았다면, 그것이 정답으로 가는 방향이 될 것이다.
우선 홀수들에서는 $2^d = 1$이다. $2^d$의 개수를 세어보면, $32$가 1개, $16$이 1개, $8$이 3개, $4$가 5개, $2$가 10개, 나머지는 $1$이다. 이것을 다시 표로 그려보면 아래와 같다.
| $2^d$ 수 | 목록 |
|---|---|
| 32 | $32$ |
| 16 | $16, \cancel{32}$ |
| 8 | $8, \cancel{16}, 24, \cancel{32}, 40$ |
| 4 | $4, \cancel{8}, 12, \cancel{16}, 20, \cancel{24}, 28, \cancel{32}, 36, \cancel{40}$ |
| 2 | $2, \cancel{4}, 6, \cancel{8}, 10, \cancel{12}, 14, \cancel{16}, 18, \cancel{20}, 22, \cancel{24}, 26, \cancel{28}, 30, \cancel{32}, 34, \cancel{36}, 38, \cancel{40}$ |
이 표를 보고 깨달을 게 있다면 그대로 구현해보도록 하자.
$S(40)$의 경우, 가능한 수들 중 $2^d$의 값을 가장 크게 나타낼 수 있는 값은 $32$로, 그 수는 $32$가 된다. 이를 수식으로 표현하면 $40 / 32 = 1.$xxx 라고 표현할 수 있다. 그 다음으로는 $16$인데, $40 / 16 = 2.$xxx 가 된다. $16$과 $32$ 2개가 존재하는데, $32$는 이미 앞에서 사용되었으므로 $16$만 선택되어 1개라고 얘기하는 것이다.
규칙을 알겠는가? 어떤 수 $x$가 있을 때, $S(x) = \sum_{i=60}^{0} \text{floor}(\frac{x}{2^i}) - cnt(\text{previous})$라는 것이다! 이것을 $a-1$와 $b$에 대해서 계산하고 빼기만 하면 답을 얻어낼 수 있는 것이다.
- 참고 알고리즘 :
코드
사용 언어 : C
최종 수정일 : 2023 / 12 / 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
typedef long long ll;
const int MAX_DIGIT = 60;
ll solve(ll x) {
if (x == 0) {
return 0;
}
ll ret = 0;
ll cnt = 0;
for (int i = MAX_DIGIT; i >= 0; --i) {
ll std = ((ll)1 << i);
ll candidate = (x / std) - cnt;
ret += std * candidate;
cnt += candidate;
}
return ret;
}
ll a, b;
int main() {
scanf("%lld %lld", &a, &b);
printf("%lld", solve(b) - solve(a - 1));
return 0;
}