题目 https://www.luogu.org/problem/P4161
DP
根据题意, 可以发现 N 个数可以组成若干个环
设组成了 K 个环, 每个环的长度为 L[ i ], 设 lcm(l[1],l[2].....,l[k])为 A, 对 A 分解质因数,
现在我们可以得到一个结论:
如果 那么就不合法
推到现在, 我们就能得出一个 DP
设 为枚举到第 i 个质数, 和为 j 的方案数
那我们就可以得出方程转移式
可以把二维滚成一维
上代码
- #include<cstdio>
- #include<cstring>
- using namespace std;
- bool vis[2000];
- long long tot,n,f[1500],b[1500];
- void init()// 筛 N 以内的素数
- {
- memset(vis,true,sizeof(vis));
- tot=0;
- for (int i=2;i<=n;i++)
- {
- if (vis[i]==true)
- {
- b[++tot]=i;
- for (int j=i+i;j<=n;j+=i)
- vis[j]=false;
- }
- }
- }
- int main()
- {
- scanf("%lld",&n);
- init();
- f[0]=1;
- for (int i=1;i<=tot;i++)
- {
- for (int j=n;j>=1;j--)
- {
- int k=1;
- while (k*b[i]<=j) f[j]+=f[j-b[i]*k],k*=b[i];
- }
- }
- long long ans=0;
- for (int i=1;i<=n;i++)
- ans+=f[i];
- printf("%lld\n",ans+1);
- }
来源: http://www.bubuko.com/infodetail-3149875.html