正文

bzoj1025(SCOI2009)游戏——唯一分解的思路与应用

IP云
IP云V管理员/1 阅读
09/17
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1025

可以认为对应的值之间连边，就连成了一个有一个或几个环的图。列数就是每个环里点数的lcm的和+1。

所以问题转化为和为n的数列的lcm种类数。

然后就看了TJ。这个人写得真的很好。https://www.cnblogs.com/phile/p/4473192.html

关键点就是将思路改成“判断这个x是不是可行（是否可以是和为n的数的lcm，因为可以有任意个1，所以也就是是否可以是和<=n的数的lcm）”。

从这个角度入手，每一个x都可以唯一分解，然后lcm是它的那些数就是一个或几个质数的幂（不能把一个质数的幂拆开，那样lcm就会小一些）；

只要某一种幂的组合的和<=n就行了。于是考虑最小的和，发现是……（详见那个人的博客）

可知质数最大不超过n。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=;
int n,pri[N],cnt;
long long ans,dp[N][N];
bool vis[N];
void init()
{
for(int i=;i<=n;i++)
{
if(!vis[i])pri[++cnt]=i;
for(int j=;j<=cnt&&i*pri[j]<=n;j++)
{
vis[i*pri[j]]=;
if(i%pri[j]==)break;
}
}
}
int main()
{
scanf("%d",&n);
init();dp[][]=;
for(int i=;i<=cnt;i++)
{
for(int k=;k<=n;k++)dp[i][k]=dp[i-][k];/////还可以不用这个质数！
for(int j=pri[i];j<=n;j*=pri[i])
for(int k=j;k<=n;k++)
dp[i][k]+=dp[i-][k-j];
}
for(int i=;i<=n;i++)ans+=dp[cnt][i];
printf("%lld",ans);
return ;
}