題目:給出1-N這N個數,問有多少個子集,集合裡的lcm是大於等於m的
可以發現m的范圍是很大的,而且1-N的子集也是很多的2^N-1個。
覺得會是DP,但是由於數據范圍太大,而無從下手。
其實可以發現的是雖然子集很多,但是LCM的值沒有那麼多,所以可以用map保存i-1個數的時候時的所有lcm值
這樣就可以轉移了
map<LL,LL>dp[i]。表示i個數,可以有it->second種情況組成it->first。
[cpp]
#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;
}
#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;
}