HDU 4028

線性離散化DP。。。表示不會。。如果直接用數組存放會爆掉內存的。。所以用map。
DP[i][j]是以第i個指針為結束的最小公倍數j的方案數。
typedef    map<LL,LL>mp;     第一個表示第i個指針為結束的最小公倍數j，第二個為以第i個指針為結束的最小公倍數j的方案數
下面是AC代碼：
[cpp] 
#include<iostream> 
#include<map> 
using namespace std; 
 
#define LL __int64  
LL m; 
int n; 
typedef map<LL,LL> mp; 
mp dp[45];                        //離散化DP，DP[i][j]是以第i個指針為結束的最小公倍數j的方案數。 
 
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 DP(){ 
    int i; 
    dp[1][1]=1; 
     
    for(i=2;i<=40;i++){ 
        dp[i]=dp[i-1]; 
        dp[i][i]+=1; 
         
        for(mp::iterator it=dp[i-1].begin();it!=dp[i-1].end();it++){ 
            LL t=lcm(it->first,i); 
             
            dp[i][t]+=it->second; 
        } 
         
    } 
     
     
} 
 
int main() 
{ 
    int T,t; 
    DP(); 
    scanf("%d",&T); 
    for(t=1;t<=T;t++) 
    { 
        scanf("%d%I64d",&n,&m); 
        printf("Case #%d: ",t); 
        LL ans=0;    www.2cto.com
        for(mp::iterator i=dp[n].begin();i!=dp[n].end();i++) 
            if(i->first>=m)ans+=i->second; 
            printf("%I64d\n",ans); 
    } 
    return 0; 
} 
作者：w00w12l