2로 나누어 지지 않는 수(홀수)는 20=1인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.
그러면 여기서 홀수의 개수는 어떻게 구할까 ?
ceil(20/2) = 10
| 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 |
4로 나누어 지지 않는 수는 21=2인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.
그러면 여기서 4로 나누어 지지 않는 수의 개수는 어떻게 구할까 ?
ceil(10/2) = 5
| 4 | 8 | 12 | 16 | 20 |
8로 나누어 지지 않는 수는 22=4인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.
그러면 여기서 8로 나누어 지지 않는 수의 개수는 어떻게 구할까 ?
ceil(5/2) = 3 (이런 경우 때문에 올림을 해야한다)
| 8 | 16 |
16로 나누어 지지 않는 수는 23=8인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.
그러면 여기서 8로 나누어 지지 않는 수의 개수는 어떻게 구할까 ?
ceil(2/2) = 1
| 16 |
32로 나누어 지지 않는 수는 24=16인 2의 거듭제곱 꼴 중 가장 큰 약수를 가진다.
그러면 여기서 16로 나누어 지지 않는 수의 개수는 어떻게 구할까 ?
ceil(1/2) = 1
이렇게 20 ~ 24 들을 가장 큰 약수로 가지는 수들의 개수를 각각 알아봤다.
이 수를 다 더하면
110 + 25 + 43 + 81 + 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;
}
}
