P4161 [SCOI2009]游戏

传送门

首先这题的本质就是把\(n\)分成若干个数的和，求他们的\(lcm\)有多少种情况

然后据说有这么个结论：若\(p_1^{c_1}+p_2^{c_2}+...+p_m^{c_m}\leq n\)，则\(ans=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)就是一个可行的\(lcm\)

证明我不会，可以看这里

然而总感觉上面的证法有哪里不太对……

不管了反正总之dp就可以了

//minamoto

#include<bits/stdc++.h>

#define ll long long

#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)

using namespace std;

const int N=1000;

int p[N],m,n;bool vis[N+5];ll f[205][N+5];

void init(){

	fp(i,2,N){

		if(!vis[i])p[++m]=i;

		for(register int j=1;j<=m&&i*p[j]<=N;++j){

			vis[i*p[j]]=1;

			if(i%p[j]==0)break;

		}

	}

}

int main(){

//	freopen("testdata.in","r",stdin);

	scanf("%d",&n),init();

	fp(i,0,m)f[i][0]=1;fp(i,1,n)f[0][i]=1;

	fp(i,1,m)fp(j,1,n){

		f[i][j]=f[i-1][j];

		for(register int k=p[i];k<=j;k*=p[i])

		f[i][j]+=f[i-1][j-k];

	}printf("%lld\n",f[m][n]);return 0;

}

巴特西

P4161 [SCOI2009]游戏

最新文章

热门文章