[SCOI2009]游戏
思路：
和为n的几个数最小公倍数有多少种。
dp即可；
代码：
#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
#define ll long long
int n,num;
ll dp[maxn][maxn],pi[maxn];
bool if_p[maxn];
void euler(int limit)
{
for(int i=;i<=limit;i++)
{
if(!if_p[i]) pi[++num]=i;
for(int j=;pi[j]*i<=limit&&j<=num;j++)
{
if_p[i*pi[j]]=true;
if(i%pi[j]==) break;
}
}
}
int main()
{
scanf("%d",&n),euler(n);
dp[][]=;
for(int i=;i<=num;i++)
{
for(int v=;v<=n;v++)
{
dp[i][v]=dp[i-][v];
for(ll pos=pi[i];pos<=v;pos*=pi[i])
{
dp[i][v]+=dp[i-][v-pos];
}
}
}
ll ans=;
for(int i=;i<=n;i++) ans+=dp[num][i];
cout<<ans+;
return ;
}
![[转]八款开源Android游戏引擎](https://www.kunjuke.com/file/css/thumb/4.jpg/280-180.jpg)
