题解 | 智乃的数字

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
using PII=pair<ll,ll>;
using PIII=pair<int,pair<int,int>>;
const ld ESP = 1e-10;
const ld PI = acosl(-1);
const int N=5e5+10;
const int M=2e5+10;
// const int mod = 1000000007;
const int mod = 998244353;
//随机化
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, 1000000000);

void solve(){
    int k;
    cin>>k;
    ll L=1,R=1e12,ans=-1;
    while(L<=R){//依旧二分一下，因为有单调性，打表找一下规律发现 如果个位是1 7 ，那么前面的数位和要对三模得2 如果 如果个位是3 9 ， 那么前面的数位和要对三模得0 然后个位为5 前面的数字没有限制 然后二分一下mid的时候前面有多少满足的数就行了
        ll mid=(L+R)>>1;
        ll f=mid/10;
        ll res=f+(mid%10>=5);//个位为5
        if(f%3==2){//前面的数位和要对三模得2
            res+=(f/3)*4+2 ;
            res+=(mid%10>=1);
            res+=(mid%10>=7);
        }
        else if(f%3==1){//前面的数位和要对三模得1
            res+=(f/3)*4+2;
        }else {//前面的数位和要对三模得0
            res+=(f/3)*4;
            res+=(mid%10>=3);
            res+=(mid%10>=9);
        }
        if(res>=k){
            ans=mid;
            R=mid-1;
        }else{
            L=mid+1;
        }
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
    return 0;
}