C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2019-05-13 17:01:12

#include<cstdio>
using namespace std;
#define ll long long
int a[69];
ll dp[69][2][2];
ll dfs(int pos, int pre2, int pre1, bool limit){
	if(-1==pos)	return 1;
	if(!limit&&dp[pos][pre2][pre1])	return dp[pos][pre2][pre1];
	int up=limit?a[pos]:1;
	ll re=0;
	for(int i=0; i<=up; ++i){
		if(1==pre2&&1==i)	continue;
		re+=dfs(pos-1, pre1, i, limit&&i==a[pos]);
	}
	if(!limit)	dp[pos][pre2][pre1]=re;
	return re;
}
ll solve(ll x){
	int pos=0;
	while(x){
		a[pos++]=x%2;
		x/=2;
	}
	return dfs(pos-1, 0, 0, true);
}
int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		ll l, r;
		scanf("%lld%lld", &l, &r);
		printf("%lld\n", solve(r)-solve(l-1));
	}
	return 0;
}

C++ 解法, 执行用时: 9ms, 内存消耗: 376K, 提交时间: 2021-06-12 22:46:47

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,a,b;
ll x[109],nx;
ll dp[109][5];
ll dfs(ll n,ll zt,bool limit)
{
	if(n==0) return 1;
	if(dp[n][zt]&&!limit) return dp[n][zt];
	ll mx=limit?x[n]:1;
	ll ans=0;
	for(int i=0;i<=mx;i++)
	{
		if(i==1)
		{
			if(zt<2) ans+=dfs(n-1,(zt*2)+1,limit&&i==mx);
		}
		else ans+=dfs(n-1,zt%2*2,limit&&i==mx);
	}
	return limit?ans:dp[n][zt]=ans;
}
ll solve(ll y)
{
	nx=0;
	while(y) x[++nx]=y&1,y>>=1;
	return dfs(nx,0,1);
}
int main()
{
	cin>>t;
	while(t--)
	{
		scanf("%lld%lld",&a,&b);
		printf("%lld\n",solve(b)-solve(a-1));
	}
	return 0;
}