https://www.acmicpc.net/problem/9527
9527호: 1의 수를 센다.
두 자연수 A와 B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 나타낼 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = 1의 개수 x가 이진법으로 표현될 때.
www.acmicpc.net
해결책
내가 시간을 낭비한 문제…
먼저 각 비트에서 1의 수를 세었습니다.
1 = 1개
10 = 2
100 = 5
1000 = 13
나는 여기서 규칙을 찾아야 했다.
먼저 10에서 100으로 증가할 때의 점프 수를 고려해 봅시다.
10, 11
오직,
100에서 1000으로 증가할 때
100, 101, 110, 11.
100에서 1000으로 증가할 때
처음 1을 제거하고 보면
00, 01, 10, 11 오전.
굵은 글씨체를 보면 이미 계산된 값임을 알 수 있습니다.
(100에서 1000으로 갈 때)
10부터 1까지 세는 숫자로 구성되어 있음을 알 수 있습니다.
나는 그것을 얻을 수 있었다 arr(i) = arr(i-1)*2 -1 + (1LL<<(i-1)).
입력 숫자에서 총합 1을 계산하는 방법
비트 단위로 읽는 중 1이 나오면
이전에 1의 수를 세었으므로 해당 배열의 값을 더합니다.
그런데 그 비트에서 처음 1을 보고 계산을 했다면 그 이후에 나오는 1비트에 대해서는 아직 계산을 하지 않은 것입니다.
나는 그래서
현재 비트 + {(값 – 현재 비트 값)}에서 1의 발생 횟수.
{ 예: 1010의 경우
1000부터 //여기까지 계산.
1001,//여기부터는 세지 않습니다.
1010
-> 10에서 8을 빼면 2가 됩니다.
–> 0010 비트가 계산되지만
1001
1010
에 대해 계산되지 않음
따라서 현재 값 – 현재 비트 값을 주어 구할 수 있습니다.
}
암호
#define ll long long int
#include <iostream>
using namespace std;
ll arr(66);
ll A, B;
ll getCnt(ll num) {
ll cnt = 0;
for (int i = 62; i >= 0; i--) {
if ((1LL << i) & num) {
num -= (1LL << i);
cnt += arr(i) + (num);
}
}
return cnt;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
arr(0) = 1;
arr(1) = 2;
for (int i = 2; i < 63; i++) {
arr(i) = arr(i - 1) * 2 - 1 + (1LL << (i - 1));
}
cin >> A >> B;
cout << getCnt(B) - getCnt(A - 1) << "\n";
}