智乃的数字【牛客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;}