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
     
      #include
      
       #define R register intconst 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