2021牛客多校9.H.Happy Number 思维规律

2021牛客多校9.H.Happy Number 😊 | Powered By HeartFireY

Problem Description

题目大意：快乐数是由" 2 , 3 , 6 2,3,6 2,3,6"组成的数字，且不能包含其他的数字，求第 n n n个快乐数。

自信满满的写了个三进制…发发现样例都过不了，然后发现。。。跟三进制没啥关系。

枚举一下前几个快乐数，发现最后一位是 236 236 236​​循环,有第二位的数字开始算,第二位是 222333666 222333666 222333666​​，即为 3 1 3^1 31​​个 2 2 2​​、 3 1 3^1 31​​个 3 3 3​​、 3 1 3^1 31​​个 6 6 6​​循环，第三位的 222222222333333333666666666 222222222333333333666666666 222222222333333333666666666就是 3 2 3^2 32​​个 2 2 2​​、 3 2 3^2 32​​个 3 3 3​​、 3 2 3^2 32​​个 6 6 6​​​​循环…以此类推循环。

Accepted Code

#include 
#define int long long
using namespace std;

const int N = 1e5 + 5;
int a[N] = {6, 2, 3, 6}, b[N];

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    int base = 3, tot = 0;
    while (n > 0){
        int now = (n - 1) % base + 1;
        now = (now + (base / 3) - 1) / (base / 3);
        b[++tot] = a[now];
        n -= base;
        base *= 3;
    }
    for (int i = tot; i >= 1; i--) cout