首页 > 代码库 > UVALive 6527 Counting ones dfs(水

UVALive 6527 Counting ones dfs(水

题目链接:点击打开链接




#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
ll re;
vector<int> p;
void dfs(int dep, int g) {
	if (dep == 0)
		return ;
	if (p[dep-1] == 1) {
		re += (dep-1) * (1ll<< (dep-2));
		re += g * (1ll << (dep-1));
	}
	dfs(dep-1, g+p[dep-1]);
}
ll C(ll x) {
	if (x == 0)
		return 0;
	p.clear();
	re = 0;
	while (x>0) {
		p.push_back(x%2);
		x /= 2;
	}
	for (int i = 0; i < (int)p.size(); ++i)
		re += p[i];
	dfs(p.size(), 0);
	return re;
}
int main() {
	ll A, B;
	while (~scanf("%lld%lld", &A, &B))
		printf("%lld\n", C(B) - C(A-1));
	return 0;
}


UVALive 6527 Counting ones dfs(水