문제링크
https://www.acmicpc.net/problem/1407
문제
풀이
범위가 1<=A<=B<=10^15 이므로 일일히 더할 수는 없다고 생각했습니다.
그래서 어떤 규칙이 있나 찾아보았습니다.
1
2
3
4
5
6
7
8
9
여기서 2로 나누어 떨어지지 않는 수는
=> ceil(9/2) = 5개 존재합니다.
나머지 수에 대해
2
4
6
8
4로 나누어 떨어지지 않는수는
=> ceil(4/2) => 2개 존재합니다.
다시 나머지 수에 대해
4
8
8로 나누어 떨어지지 않는수는
=> ceil(2/2) => 1개 존재합니다.
8
16으로 나누어 떨어지지 않는 수는
=> ceil(1/2) => 1개 존재합니다.
- 따라서 1~9 에서 각 수의 약수 중 가장 큰 2의거듭제곱꼴 약수를 모두 더한값은 1x5 + 2x2 + 4x1 + 8x1 = 17입니다.
1~N에 포함된 각 수에서 가장 큰 2의 거듭제곱꼴 약수를 모두 더한 값을 반환해주는 함수를 F(N)이라고 합시다.
그러면 A~B 의 범위에서는 F(B)-F(A-1) 을 이용해 답을 도출할 수 있습니다.
시행착오
- 분할정복으로 풀리나 싶어서 도전해봤는데 복잡해져서 포기했습니다 ㅎㅎ
- 형변환 때문에 ceil함수 썼다가 몇 번 틀렸습니다.
코드
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
ll a, b;
ll solve(ll a) {
ll ans = 0, temp = 1;
while (a != 0) {
if (a % 2 != 0) ans += ((a / 2) + 1)*temp;
else ans += (a / 2)*temp;
a /= 2;
temp *= 2;
}
return ans;
}
int main(void) {
cin >> a >> b;
cout << solve(b) - solve(a - 1);
}후기
너무 복잡하게 생각했다 !
