ywy神犇太巨辣！！一下就明白了！！
题意：求$lcm(a_1,a_2,...,a_k)$的种类，其中$\Sigma\space a_i <=n$，$a_i$相当于环长
此处的$DP$，相当于是在求$lcm(a_1,a_2,...,a_k)$按算术基本定理分解的式子的种类。
感性理解一下，一堆>=2的数，加起来一定比乘起来小，但是我们又要保证他们互质（否则就亏了，不如同时去掉gcd），所以就每个数就是一个质数的幂。
所以这一堆数大致就是形如$p_i^{k_i}$这种样子的
所以可以背包转移：把每个质数当做物品，注意转移时的顺序，用质数$p$转移时不能访问已经经过$p$转移过的（类似01背包的倒序循环），否则不满足互质；
#include<cstdio> #include<iostream> #define R register int const int N=1010; using namespace std; int n,cnt,pri[N]; bool v[N]; long long f[N],ans; inline void PRI() { for(R i=2;i<=n;++i) { if(!v[i]) pri[++cnt]=i; for(R j=1;j<=cnt&&i*pri[j]<=n;++j) { v[i*pri[j]]=true; if(i%pri[j]==0) break; } } } signed main() { scanf("%d",&n); f[0]=1; PRI(); for(R i=1;i<=cnt;++i) for(R j=n;j>=0;--j) for(R k=pri[i];k<=j;k*=pri[i]) f[j]+=f[j-k]; for(R i=0;i<=n;++i) ans+=f[i]; printf("%lld\n",ans); }
2019.05.25
Luogu P4161 [SCOI2009]游戏 数论+DP
原文：https://www.cnblogs.com/Jackpei/p/10923147.html