思路与算法

对应关系是一个排列，重复直到还原的周期为各循环长度的LCM；排数再加1，但不同周期与不同排数一一对应。一个周期由每个素数的最大幂唯一决定，能用的最少点数是这些素数幂的和。以每个素数为一组，任选不选或一个不超过N的幂，分组背包按所需点数计数，最后求≤N总数。使用自实现十进制分块高精加法。

正确性说明

任意循环长可拆成互质最大素数幂，它们之和不超过原循环长；跨循环只保留每个素数最高幂，费用进一步不增。因此任何可行周期的素数幂之和≤N。反之用这些幂分别作循环，剩余点固定即可实现该LCM。唯一素数幂选择对应唯一周期，分组背包无重无漏。

复杂度

设π(N)组、每组有log_p N个选项，高精位数D。DP数组初始化O(N)，转移O(DNΣp log_p N)，筛素数O(NloglogN)，空间O(DN)；N≤1000，不依赖64位结果假设。

易错点

不选任何素数幂对应周期1，用固定点可实现，也要计入。组内只能选一个幂，不能当完全背包累计同一素数不同幂。输出的是种数，不是最大周期。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Big {
    vector<unsigned> a;
    Big(unsigned x = 0) {
        if (x)
            a.push_back(x);
    }
    void add(const Big &b) {
        unsigned long long c = 0;
        size_t n = max(a.size(), b.a.size());
        a.resize(n);
        for (size_t i = 0; i < n; i++) {
            c += a[i] + (i < b.a.size() ? b.a[i] : 0ULL);
            a[i] = c % 1000000000;
            c /= 1000000000;
        }
        if (c)
            a.push_back(c);
    }
    void print() {
        if (a.empty()) {
            cout << 0;
            return;
        }
        cout << a.back();
        for (int i = (int)a.size() - 2; i >= 0; i--)
            cout << setw(9) << setfill('0') << a[i];
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> prime;
    vector<bool> is(n + 1, true);
    for (int i = 2; i <= n; i++)
        if (is[i]) {
            prime.push_back(i);
            for (int j = i + i; j <= n; j += i)
                is[j] = false;
        }
    vector<Big> dp(n + 1);
    dp[0] = Big(1);
    for (int p : prime) {
        vector<Big> ndp = dp;
        for (int x = p; x <= n;) {
            for (int i = 0; i + x <= n; i++)
                ndp[i + x].add(dp[i]);
            if (x > n / p)
                break;
            x *= p;
        }
        dp.swap(ndp);
    }
    Big ans;
    for (auto x : dp)
        ans.add(x);
    ans.print();
    cout << '\n';
}