• 周二. 9月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

#01背包#洛谷 4161 [SCOI2009]游戏

admin

11月 28, 2021

题目

(n) 拆成若干个正整数的和,
问这些正整数的LCM有多少种
(nleq 10^3)


分析

考虑这个(LCM)一定是1或者由若干个质数的指数幂相乘得到的,
那么可以设(dp[i])表示选择质数或其指数幂的和为(i)的方案数,
直接01背包即可,答案为(sum_{i=0}^ndp[i])


代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=1011;
long long dp[N];
int v[N],prime[N],n,Cnt;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
signed main(){
	n=iut();
	for (rr int i=2;i<=n;++i)
	if (!v[i]){
		prime[++Cnt]=i;
		for (rr int j=i+i;j<=n;j+=i)
		    v[j]=1;
	}
	dp[0]=1;
	for (rr int i=1;i<=Cnt;++i)
	for (rr int j=n;j>=prime[i];--j){
		rr int p=prime[i];
		for (;j>=p;p*=prime[i]) 
		    dp[j]+=dp[j-p];
	}
	for (rr int i=1;i<=n;++i) dp[0]+=dp[i];
	return !printf("%lld",dp[0]);
}

发表回复

您的电子邮箱地址不会被公开。