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

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

• 문제
• 풀이

 

---

문제

문제 내용

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

1407번: 2로 몇 번 나누어질까

---

풀이

나의 풀이

- 정수론 문제였는데 아이디어가 한 번 생각 안 나니까 계속 헤매서 어려웠다.

- 다른 사람들의 풀이를 봐도 잘 이해가 가지 않아 속상했으나 아래 블로그 글의 풀이를 보고 단번에 이해가 됐다.

직관적으로 풀 수 있는 능력을 많이 기를 수 있도록 노력해야겠다.

(https://blog.naver.com/PostView.nhn?blogId=kerochuu&logNo=222119167868&parentCategoryNo=6&categoryNo=8&viewDate=&isShowPopularPosts=false&from=postView)

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

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

        long fromRange = Long.parseLong(st.nextToken());
        long toRange = Long.parseLong(st.nextToken());

        long answer = CalcBinarySqureRoot(toRange) - CalcBinarySqureRoot(fromRange-1);

        System.out.printf("%d", answer);
    }

    public static long CalcBinarySqureRoot(long n) {
        long result = n;

        for(long i=2; i<=n; i<<=1) // 2의 배수만큼씩 증가
            result += (n/i)*(i>>1); // 2의 개수 구하기

        return result;
    }
}