本文共 955 字，大约阅读时间需要 3 分钟。
/** 题意：给你1~n个数，问你它的子集内有多少集合的Lcm（最小公倍数） 大于等于m的； 题解：DP离散化，用map映射一下， map dp[i]。表示i个数，可以有it->second种情况组成it->first。 也算是长姿势了，map的用法感觉懂得还是太少了**/#include #include #include #include #include #include #include #include #include using namespace std;typedef __int64 LL;map dp[50];map ::iterator it;LL m,n;LL gcd(LL a,LL b){ return b == 0 ? a : gcd(b,a%b);}LL Lcm(LL a,LL b){ return a * b / gcd(a,b);}void init(){ dp[1][1] = 1; for(LL 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个数 } }}int main(){ init(); int t,ca = 1; cin >> t; while(t--){ cin >> n >> m; LL ans = 0; for(it = dp[n].begin();it != dp[n].end();it++)//统计一下n个数组成子集满足条件的个数 if(it->first >= m) ans += it->second; printf("Case #%d: %I64d\n",ca++,ans);// cout << ans << endl; } return 0;}
转载地址：http://fcsgi.baihongyu.com/