题解 | 智乃的数字

#include<iostream>
using namespace std;
typedef long long ll;
ll check(ll x){
    ll m10=(x+5)/10;
    ll m6=(x+3)/6;
    ll m=(x+15)/30;
    return m10+m6-m;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int k;
        cin>>k;
        ll res=0;
        ll l=1,r=1e10;
        while(l<r){
            ll mid=l+r>>1;
            if(check(mid)>=k){
                res=mid;
                r=mid;
            }else l=mid+1;
        }
        cout<<res<<"\n";
    }
    return 0;
}

看到或 两种情况 考虑容斥原理

在找第k个智数时 因为k充分大 故考虑二分

我们不去寻找第k个智数为多少 反面思考 在给定k时,去找满足 最小拥有k个智数的数为多少 (把单个的k转为连续的前k个数)