链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1025
神犇题解：http://blog.csdn.net/PoPoQQQ/article/details/40537227
解题报告
这题把数学模型抽象出来就是
取一些数ai，要求∑ai<=n
求这些数的最小公倍数有多少种不同的可能
我自己就只想到这里就想不出来了…
果然还是得膜拜神犇…
逆向考虑：考虑一个数能否被凑出来
假如将其质因数分解之后为：p1^c1 * p2 ^ c2 * …… * px^cx
并且∑pi^ci <= n，那么一定可以凑出来
考虑最小公倍数的定义：至少有一个数中包含了pi^ci
所以这样判断是没有问题的
于是从小到大考虑质因数，使用分组背包进行转移
f[i][j]表示已经考虑了前i个质数，\(\sum\limits_{k = 1}^i {p_k^{{c_k}}} = j\)
时间复杂度O(n^2)
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1000+9;
LL n,tot,pri[N],vout,f[N][N];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void prework() {
for (int i=2;i<=n;i++) {
bool tag = 1;
for (int j=2;j<i;j++) {
if (i % j == 0) {
tag = 0;
break;
}
}
if (tag) {
pri[++tot] = i;
}
}
f[0][0] = 1;
}
int main(){
n = read();
prework();
for (int i=1;i<=tot;i++) {
for (int j=0;j<=n;j++) {
f[i][j] += f[i-1][j];
for (int k=pri[i];k<=j;k*=pri[i]) {
f[i][j] += f[i-1][j-k];
}
}
}
for (int i=0;i<=n;i++)
vout += f[tot][i];
printf("%lld\n",vout);
return 0;
}
254121 708678Sewing Machines […]any time to read or go towards the content or possibly internet web sites we surely have associated with[…] 206026
948249 406090Average In turn sends provides may be the frequent systems that give the opportunity for ones how does a person pick-up biological, overdue drivers, what one mechanically increases the business. Search Engine Marketing 31996
723362 950702Your post is truly informative. Far more than that, it??s engaging, compelling and well-written. I would desire to see even much more of these types of excellent writing. 356309
858651 255832Woh I enjoy your content material , saved to favorites ! . 952344
923678 304857Merely wanna input on few common issues, The internet site style is perfect, the subject material is rattling superb : D. 110198
677042 50990Most what i read online is trash and copy paste but i think you offer something different. Maintain it like this. 981225
358279 388965An fascinating discussion may be valued at comment. I do believe which you basically write read much more about this subject, it may not often be a taboo topic but normally persons are too couple of to dicuss on such topics. To a higher. Cheers 496621
259795 294920This is a excellent blog, would you be involved in performing an interview about just how you designed it? If so e-mail me! 993708
738568 139967I want going to comment as this posts a bit old now, but just wanted to say thanks. 269050
394611 718490Just wanna input on couple of common items, The web site design is perfect, the articles is really fantastic : D. 249265
710187 612071woah i like yur internet site. It truly helped me with the information i wus looking for. thank you, will save. 389236
474612 272473Some truly good stuff on this web internet site , I love it. 980608
948448 319944Hello! I just wish to give an enormous thumbs up for the very good details you may have right here on this post. I can be coming once more to your blog for far more soon. 210450
Prior to becoming a member of an illusion baseball league, make sure you are absolutely committed. You can’t give up the league at the center. You can not be there at the start and after that cease to the midsection. Stopping could have a negative influence on the drafting together with other players’ impression people.
Play with your own style. You shouldn’t commit the game upstaging your teammates or thinking of just you, but there are actually moment within a soccer game where your individuality can stand out, especially soon after a remarkable deal with or touchdown. Do you have a specific fist push or shuffle party you would like to take out. Do it! Get the teammates involved as well.
Even should you not play in every single game, study the playbook every day. Anytime you do have a free min, check out the performs. You need to anticipate to get tossed into the video game whenever you want. Who knows when a person can get hurt or even your instructor desires to provide the chance to perform. Learning the performs will prevent you from hunting foolish on the field.
Exercise all you could. Football might appear straightforward when watching it on tv, but that’s far from the reality. It’s a very actually stressful activity which get a great deal of human brain energy. You have to keep in mind habits and think in your toes with little recognize to be successful. All this takes exercise.
Understand by watching the advantages. This doesn’t mean just seated around and finding this game along with your friends. Get a gamer who plays the identical place as you may and enjoy the direction they play. Analyze the way that they relocate their feet, and what selections they make in the area. Make an effort to replicate them in your own online game.