【2018/08/19测试T1】【SOJ 1002】Number

【题目】

题目描述：

如果一个数能够表示成两两不同的 3 的幂次的和，就说这个数是好的。
比如 13 是好的，因为 13 = 9 + 3 + 1 。
又比如 90 是好的，因为 90 = 81 + 9 。
现在我们用 a[ i ] 表示第 i 小的好数。
比如 a[ 1 ] = 1, a[ 2 ] = 3, a[ 5 ] = 10 。
给定 L，R，请求出 a[ L ] 到 a[ R ] 的和 mod 。

输入格式：

第一行一个整数 T，表示数据组数。
接下来 T 行，每行两个整数 L，R 表示一组询问。

输出格式：

输出 T 行，每行为一个整数，表示相应询问的答案。

样例数据：

输入

5
1 3
3 3
4 5
6 7
2 5

输出

8
4
19
25
26

备注：

【数据范围】
对 30% 的输入数据：1 ≤ T ≤ 100；R ≤ 1000 。
对 100% 的输入数据：1 ≤ T ≤ 100000；1 ≤ L ≤ R ≤  。

 

【分析】

同桌大佬的博客%%%

前桌大佬的博客%%%

前前桌大佬的博客%%%

首先说一下如何快速求第 i 小的好数吧，就是将 i 转换成二进制，再将这个二进制当做三进制转换成十进制，比如说 5，它的二进制是 101，把他当做三进制后转回来就是 10

我们相当于是要按位来计算比 a[ i ] 小的好数的和，是和数位DP差不多的思想，不过要简单

然后推荐去看大佬的博客，本蒟蒻觉得我讲不清楚……

 

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
unsigned int pow[100],sum[100];
unsigned int solve(long long x)
{
	int i;
	unsigned int ans=0,now=0;
	for(i=63;i>=1;--i)
	{
		if((1ll<<i)&x)
		{
			ans+=sum[i-1]*(1ll<<(i-1));
			ans+=now*(1ll<<i);
			ans+=pow[i];
			now+=pow[i];
		}
	}
	if(x&1)
	  ans+=now+1;
	return ans;
}
int main()
{
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	int t,i;
	long long l,r;
	scanf("%d",&t);
	pow[0]=1,sum[0]=1;
	for(i=1;i<=64;++i)
	{
		pow[i]=pow[i-1]*3;
		sum[i]=sum[i-1]+pow[i];
	}
	for(i=1;i<=t;++i)
	{
		scanf("%lld%lld",&l,&r);
		printf("%lld\n",solve(r)-solve(l-1));
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}