BOJ_1407_2로 몇 번 나누어질까

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

문제 링크

성능 요약

메모리: 14312 KB, 시간: 100 ms

분류

수학

제출 일자

2024년 10월 22일 05:09:50

문제 설명

자연수 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≤B)가 주어지면, A 이상 B 이하의 모든 자연수에 대해서, 그 자연수의 모든 약수 중 2의 거듭제곱 꼴이면서 가장 큰 약수들의 총 합을 구하는 프로그램을 작성하시오. 즉 아래와 같은 수식의 값을 구해야 한다.

f(A) + f(A+1) + ... + f(B-1) + f(B)

입력

첫째 줄에 자연수 A와 B가 빈 칸을 사이에 두고 주어진다. (1≤A≤B≤10^15)

출력

첫째 줄에 구하고자 하는 수를 출력한다.

문제 풀이

1의배수 - 2의배수 - 4의배수 이런식으로 좁혀 찾아나가고 이렇게 새로 찾으면 /2를 더해주면 된다. 4를 찾으면 2를 더했으므로 나머지 2 더해주기 이런식.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;
public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static long A, B;
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}
	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());
		A = Long.parseLong(st.nextToken());
		B = Long.parseLong(st.nextToken());
		long res = calNum(B) - calNum(A-1); 
        bw.write(String.valueOf(res));
		bw.flush();
		bw.close();
		br.close();
	}
	private long calNum(long num) {
		long tmp = num;
		for(long i=2; i<=num; i<<=1) {
			tmp += (num/i) * (i>>1);
		}
		return tmp;
	}
}