题解 | #智乃的数字#

这是一个非常经典的数论找规律问题。既然是找第 个数，且 很大（），我们不能一个一个数去数，必须找规律。

我们考察一下奇数序列，看看哪些是“智数”。 我们需要关注 3 和 5 的最小公倍数。。 但因为我们只看奇数，奇数的周期是 2，所以我们应该观察 范围内的规律。

让我们列出 1 到 30 之间的所有整数，筛选出符合条件的“智数”：

1. 1：不是
2. 3：是 (3的倍数) -> 第1个
3. 5：是 (5的倍数) -> 第2个
4. 7：不是
5. 9：是 (3的倍数) -> 第3个
6. 11：不是
7. 13：不是
8. 15：是 (3和5的倍数) -> 第4个
9. 17：不是
10. 19：不是
11. 21：是 (3的倍数) -> 第5个
12. 23：不是
13. 25：是 (5的倍数) -> 第6个
14. 27：是 (3的倍数) -> 第7个
15. 29：不是

发现规律： 在每 30 个自然数（或者说每15个奇数）的周期里，恰好有 7 个“智数”。 这 7 个数相对于周期的偏移量（Offset）分别是： {3, 5, 9, 15, 21, 25, 27}

这个规律会无限循环：

• 第 1~7 个智数在 1~30 之间。
• 第 8~14 个智数在 31~60 之间（即 ）。
• 以此类推。

现在我们要找第 个智数。我们可以利用周期性直接计算。

1. 确定完整的周期数： 每 30 个数里有 7 个智数。 我们可以算出第 个智数经历了多少个完整的“7个一组”。

   为了方便计算（处理数组下标从0开始的问题），我们通常使用 来计算： (注：// 表示整数除法)

2. 确定在周期内的位置： 这个余数对应我们在 {3, 5, 9, 15, 21, 25, 27} 这个列表中的位置。

3. 计算最终结果：

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    array<int, 7> v{3, 5, 9, 15, 21, 25, 27};

    while (T--) {
        int k;
        cin >> k;
        ll cycle = (k - 1) / 7;
        ll idx = (k - 1) % 7;
        ll ans = 30LL * cycle + (ll)v[idx];
        cout << ans << endl;
    }
}