解题思路

1. 核心观察：智数的周期规律

智数定义是奇数且满足以下任一条件：

• 以 5 结尾（即 mod 10 = 5）；
• 各位数字之和是 3 的倍数（等价于自身是 3 的倍数，因为一个数是 3 的倍数 ↔ 各位和是 3 的倍数）。

通过枚举前若干智数，发现其分布存在固定周期：

• 先列出智数序列（升序）：3、5、9、15、21、25、27、33、35、39、45、51、55、57、...
• 观察间隔：从 3 开始，每 7 个智数为一组，每组内的智数与下一组对应智数的差值固定为 30（即周期长度 = 30）。第 1 组（k=1~7）：3、5、9、15、21、25、27第 2 组（k=8~14）：33（3+30）、35（5+30）、39（9+30）、45（15+30）、51（21+30）、55（25+30）、57（27+30）第 3 组（k=15~21）：63（3+60）、65（5+60）、69（9+60）、...（以此类推）

2. 周期规律验证

周期长度 30 的本质：

• 3 的倍数的奇数：公差为 6（3、9、15、21、27、33...）；
• 以 5 结尾的奇数：公差为 10（5、15、25、35、55...）；
• 两者的最小公倍数为 30，因此智数的分布周期为 30，且每个周期内恰好包含 7 个不重复的智数。

3. 公式推导

基于周期规律，第 k 个智数可通过以下步骤计算：

1. 索引转换：将 k 从 “1-based” 转为 “0-based”（k--），方便取模计算；
2. 分组计算：每组有 7 个智数，通过 t = k / 7 得到第 k 个智数所在的组号（从 0 开始）；
3. 组内定位：通过 r = k % 7 得到第 k 个智数在组内的索引（0~6）；
4. 结果计算：每组的基准偏移量为 30 * t，加上组内对应索引的智数（预存于数组），即为答案。

ACnode

#include <bits/stdc++.h>
using namespace std;
#define int long long  //避免溢出

// 预存一个周期内（7个）智数的基础值（第1组的7个智数）
int arr[7] = {3, 5, 9, 15, 21, 25, 27};

void solve()
{
    int k;
    cin >> k;
    k--;  // 1-based转0-based索引，方便取模
    int t = k / 7;  // 计算所在组号（0开始），每组7个智数
    int r = k % 7;  // 计算组内索引（0~6）
    // 每组偏移量为30*t，加上组内对应基础值
    cout << 30 * t + arr[r] << endl;
}

signed main()
{
    int qwq = 1;
    cin >> qwq; 
    while (qwq--)
    {
        solve();  // 处理每组测试
    }
    return 0;
}

时间复杂度与空间复杂度

• 时间复杂度：O (T)，每组测试用例仅需 O (1) 计算，T=1e5 时无压力；
• 空间复杂度：O (1)，仅用固定大小的数组存储 7 个基础值，无额外空间消耗。