转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526
by---cxlove
题目:给出1-N这N个数,问有多少个子集,集合里的lcm是大于等于m的
http://acm.hdu.edu.cn/showproblem.php?pid=4028
可以发现m的范围是很大的,而且1-N的子集也是很多的2^N-1个。
觉得会是DP,但是由于数据范围太大,而无从下手。
其实可以发现的是虽然子集很多,但是LCM的值没有那么多,所以可以用map保存i-1个数的时候时的所有lcm值
这样就可以转移了
map<LL,LL>dp[i]。表示i个数,可以有it->second种情况组成it->first。
#include<iostream> #include<cstdio> #include<map> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<algorithm> #include<set> #define inf 110000 #define M 10005 #define N 10005 #define Min(a,b) ((a)<(b)?(a):(b)) #define Max(a,b) ((a)>(b)?(a):(b)) #define pb(a) push_back(a) #define mem(a,b) memset(a,b,sizeof(a)) #define eps 1e-9 #define zero(a) fabs(a)<eps #define LL long long #define MOD 1000000007 using namespace std; map<LL,LL>dp[45]; map<LL,LL>::iterator it; LL gcd(LL a,LL b){ return b==0?a:gcd(b,a%b); } LL lcm(LL a,LL b){ return a/gcd(a,b)*b; } void DP(){ dp[1][1]=1; for(int i=2;i<=40;i++){ dp[i]=dp[i-1]; //不取第i个数的所有情况,先复制过来 dp[i][i]++; //只取第i个数,不能落下 for(it=dp[i-1].begin();it!=dp[i-1].end();it++) dp[i][lcm(i,it->first)]+=it->second; //然后考虑在前i-1个数的基础上加入第i个数 } } LL n,m; int main(){ DP(); int t,cas=0; scanf("%d",&t); while(t--){ scanf("%I64d%I64d",&n,&m); LL ans=0; //遍历一遍 for(it=dp[n].begin();it!=dp[n].end();it++) if(it->first>=m) ans+=it->second; printf("Case #%d: %I64d\n",++cas,ans); } return 0; }