[백준] 1407번 : 2로 몇 번 나누어질까 (C++)

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

 

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

// 1407. 2로 몇 번 나누어질까
#include <iostream>
#include <vector>
 
using namespace std;
 
long long a, b;
 
long long temp(long long n)
{
    vector<long long> vec;
    long long answer = 0; 
    long long i = 2;
    for (; i < n + 1; i *= 2)
    {
        vec.push_back(n / i);
    }
    vec.push_back(0);
    
    i /= 2;
    for (int j = vec.size() - 2; j >= 0; j--)
    {
        answer += (vec[j] - vec[j + 1]) * i;
        i /= 2;
    }
    answer += n - vec[0];
 
    return answer;
}
 
 
int main()
{
    cin >> a >> b;
    cout << temp(b) - temp(a - 1);
 
    return 0;
}
 
/*
1 2 3 4 5 6 7 8 9
x o x o x o x o x
x x x o x x x o x
x x x x x x x o x
x x x x x x x x x
 
2의 개수    - 4개
4의 개수    - 2개
8의 개수 - 1개
 
8부터 거꾸로 계산해보면.
약수 8을 가지는 수 = 1개
약수 4을 가지는 수 = 2(4) - 1(8) = 1개
약수 2을 가지는 수 = 4(2) - 2(4) = 2개
약수 1을 가지는 수 = 전체 수 - 4(2) = 5개 
*/

---

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

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