株洲建设网站制作互联网运营推广公司

株洲建设网站制作,互联网运营推广公司,童程童美少儿编程怎样收费,网站建设模智乃的数字 时间限制#xff1a;1秒 空间限制#xff1a;256M 网页链接 牛客tracker 牛客tracker 每日一题#xff0c;完成每日打卡#xff0c;即可获得牛币。获得相应数量的牛币#xff0c;能在【牛币兑换中心】#xff0c;换取相应奖品#xff01;助力每日有…智乃的数字时间限制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个智数。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefpairll,llpii;constll p1e97;constll N2e510;ll a[]{27,3,5,9,15,21,25};voidsolve(){ll k;cink;cout((k-1)/7)*30a[k%7]endl;}intmain(){ll t;cint;while(t--)solve();return0;}