Luogu P4161 [SCOI2009]游戏 数论+DP

ywy神犇太巨辣！！一下就明白了！！

---

题意：求$lcm(a_1,a_2,...,a_k)$的种类，其中$Sigmaspace 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
",ans);
}

---

2019.05.25