题解 P6280 【[USACO20OPEN]Exercise G】

· · 题解

首先这题和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;
}