H

题目描述

所有含有2或3或6的数字都定义为"快乐数”，给出一个n，求第n小的"快乐数”是多少。

~

题意分析

赛时思路：

一开始我看错题了，以为n是范围，想打表来着…… 后来一看题，打表是不可能了，就考虑有没有正解。

首先，对于每个"快乐数”都有一个共性：每个数都由2 3 6组成！

有什么发现没有？是不是有点像进制转换问题？

但是在实现代码的时候，我发现一点不一样的东西：

我们很明显的发现，出现问题了，因为0的性质十分的特殊，在进位的时候不能放在第一个。

然后这个思路pass掉了。

但是这个思路虽然不是正规的三进制，但我们可以用1 2 3（分别代表2 3 6）把进制转换的过程模拟出来！

很明显单纯枚举的话是不现实的，所以我们按照进制转换的运算规则，来确定这个数字的位数。

那么怎么确定位数呢？

乘法原理。

注意到对于n位数，每一位都有三种可能的填数方法：2 3或6。所以n位数就有3^n 种可能性。

那么如何根据n来确定位数呢？需要从1位数开始累加可能性，也就是说，等比数列求和。

为了防止被卡常，所以我提前打了个表。

```const int log3[]={0,3,12,39,120,363,1092,3279,9840,29523,88572,265719,797160,2391483,7174452,21523359,64570080,193710243,581130732};

然后我们找完多少位了，接下来我是想用n减去区间下限，然后依次从1开始枚举，模拟这一种特殊的进制运算。

然后就TLE了。

后来我又一想，依旧是可以使用进制转换的方法。

n减去区间下限以后，是这个数字在这个位数区间里面的序号。

也就是说，把这个序号转化成三进制，然后再累加到求出那个位数对应的最小数(全是11)上面。

重点，由于序号1是它本身，所以我们应当对序号采取减一操作。

然后我们就得到了一串数，只含有1 2和3。

然后再用2 3 6进行替换即可。

AC CODE （O(log3 n)）

```#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,wei,a[10000],b[10000];
const int log3[]={0,3,12,39,120,363,1092,3279,9840,29523,88572,265719,797160,2391483,7174452,21523359,64570080,193710243,581130732};
void f(int x)
{
	int wei2=wei;
	while(x)
	{
		b[wei2]=x%3;
		x/=3;
		wei2--;
	}
}
signed main()
{
	cin>>n;
	for(int i=0;;i++)
		if(n>log3[i]&&n<=log3[i+1])
		{
			wei=i+1;
			n-=log3[i];
			break;
		}
	for(int i=1;i<=wei;i++)
		a[i]=(int)1;
	n--;
	f(n);
	for(int i=1;i<=wei;i++)
		a[i]+=b[i];
	for(int i=1;i<=wei;i++)
	{
		if(a[i]==(int)1)
			cout<<2;
		if(a[i]==(int)2)
			cout<<3;
		if(a[i]==(int)3)
			cout<<6;
	}
	return 0;
}