题解 | 智乃的数字(二分）

//打表找周期过于无趣（bushi）写个二分练练手
//我们只需要求得小于mid范围内有多少奇数符合3和5的倍数即可判断mid是否合法
//思路就是这么简单
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t;
void solve(){
    int k;cin>>k;
    int l=3,r=(2*k-1)*3;//瞪眼法发现对于任意k，ans必定小于（2k-1）*3
    int ans=0;
    while(l<=r){
    	int mid=(l+r)/2;
		int c3=(mid+3)/6,c5=(mid+5)/10,re=(mid+15)/30;//分别求奇数范围内3，5的倍数以及3和5的公倍数
		int sum=c3+c5-re;
		if(sum<k) l=mid+1;//sum太少了，在大一点
		else{
			ans=mid;//sum足够大，更新ans
			r=mid-1;//在找找有没有更小的ans
		}
	}
	cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--) solve();
}