自动搬运

查看原文

来自洛谷，原作者为

	rouxQ **

搬运于2025-08-24 22:19:16，当前版本为作者最后更新于2020-04-06 10:28:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先这题和P4161几乎一模一样，（P4161要求k的个数，本题求所有k的和），所以双倍经验

然后我们来看这题，可以发现如果循环了几次可以回到原地，当且仅当形成了一个环，假如设每个环的长度是 $a_i$，那么可以发现 $k=\operatorname{lcm}a_i$，又知道 $\operatorname{lcm}$ 其实就是将那几个数分解质因数，然后取每个质数的最高次幂乘起来，所以我们可以想到枚举素数来做dp。

我们设 $f(i,j)$ 表示前 $i$ 个素数总和为 $j$ 的所有 $k$ 的总和，枚举第 $i$ 个素数的幂进行转移，因为之前并没有用过第 $i$ 个素数，所以应把上一个状态乘上 $p_i^k$，所以直接有方程 $f(i,j)=\sum f(i-1, j-p_i^k)\times p_i^k$

接着发现这个东西可以滚动数组压缩一下，于是可以省掉一维 $f(j)=\sum f(j-p_i^k)\times p_i^k$，倒序枚举即可，初始状态 $f(0)=1$，最后答案是 $\sum f(i)$

代码

#include <bits/stdc++.h>
#define ll long long//注意开long long
using namespace std;
const int N = 1e4 + 3;
bool vis[N]; vector<int> p;
ll f[N] = {1}, m;int n;
int main (){
    p.push_back(0);//让素数的下标从一开始，使后面的转移更简洁
    cin >> n >> m;
    for (int i = 2; i <= n; i++){
        if (!vis[i])p.push_back(i);
        for (int j = i * i; j <= n; j += i)vis[j] = 1;
    }//埃筛筛素数
    for (int i = 1; i < p.size(); i++)
        for (int j = n; j >= p[i]; j--){
            int tmp = p[i];
            while(tmp <= j)
                f[j] = (f[j] + f[j - tmp] * tmp % m) % m, tmp *= p[i];
        }
    ll Ans = 0;
    for (int i = 0; i <= n; i++)Ans = (Ans + f[i]) % m;
    cout << Ans << endl;
    return 0;
}