智乃的数字【牛客tracker 每日一题】
智乃的数字
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
如果一个奇数满足以下两个条件之一：
- 以5 55结尾
- 各个数位相加的和是3 33的倍数
则称它是一个"智数"
前5 55个"智数"分别为3 , 5 , 9 , 15 , 21 {3,5,9,15,21}3,5,9,15,21
现在智乃想要你给升序排序第k kk个"智数"
输入描述：
第一行输入一个正整数T ( 1 ≤ T ≤ 1 0 5 ) T(1≤T≤10^5)T(1≤T≤105)表示测试用例的组数
对于每组测试用例，在一行中输入一个正整数k ( 1 ≤ k ≤ 1 0 9 ) k(1≤k≤10^9)k(1≤k≤109)
输出描述：
对于每个问题，输出一行一个正整数，表示问题的答案
示例1
输入：
5 1 2 3 4 5输出：
3 5 9 15 21示例2
输入：
1 1000000000输出：
4285714285解题思路
通过分析“智数”的规律，发现其以7 77个为一组、每组间隔30 3030的周期性特征，先预存第一组的7 77个智数到数组a aa中（27 , 3 , 5 , 9 , 15 , 21 , 25 27,3,5,9,15,21,2527,3,5,9,15,21,25，对应组内不同位置的智数）；对于每组测试用例的k kk值，先计算组数为( k − 1 ) / 7 (k-1)/7(k−1)/7（即前面有多少个完整组），每组对应30 3030的倍数，再通过k kk%7 77得到该智数在组内的索引，最终结果为组数乘以30 3030加上数组a aa中对应索引的数值；该方法利用周期性规律避免了逐一枚举判断智数的复杂过程，单次查询时间复杂度为O ( 1 ) O(1)O(1)，适配T TT达1 e 5 1e51e5、k kk达1 e 9 1e91e9的大规模输入，高效精准输出第k kk个智数。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e5+10;ll a[]={27,3,5,9,15,21,25};voidsolve(){ll k;cin>>k;cout<<((k-1)/7)*30+a[k%7]<<endl;}intmain(){ll t;cin>>t;while(t--)solve();return0;}