hdu 4028 2011上海赛区网络赛H dp+map离散

一开始用搜索直接超时，看题解会的

 #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[];

 map<LL,LL>::iterator it;

 LL gcd(LL a,LL b){

     return b==?a:gcd(b,a%b);

 }

 LL lcm(LL a,LL b){

     return a/gcd(a,b)*b;

 }

 void DP(){

     dp[][]=;

     for(int i=;i<=;i++){

         dp[i]=dp[i-];   //不取第i个数的所有情况，先复制过来

         dp[i][i]++;      //只取第i个数，不能落下

         for(it=dp[i-].begin();it!=dp[i-].end();it++)

             dp[i][lcm(i,it->first)]+=it->second;   //然后考虑在前i-1个数的基础上加入第i个数

     }

 }

 LL n,m;

 int main(){

     DP();

     int t,cas=;

     scanf("%d",&t);

     while(t--){

         scanf("%I64d%I64d",&n,&m);

         LL ans=;

         //遍历一遍

         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  ;

 }