题意：

一个如果称作是漂亮数，当且仅当满足：

每一位上的数字是【1，9】，从高到时低数字大小降序，且有di%dj=0(i<j) 例：931

给一个区间【L,R】，问这个区间里有多少个漂亮数。

1≤L≤R≤109

 

思路：

漂亮数一看就很少。可以直接构造。

哎，，，用了DP+构造，写了好久。。。其实很简单的一个DFS构造就行了。

过些天补上代码。先贴冗长代码~

 

代码：

int T,L,R;int wei;int ans1,ans2,ans;int d[15], w[15];int dp[15][15];int calc(int x){    int cn=0;    while(x){        x/=10;        ++cn;    }    return cn;}void dfs(int pos,bool state){    if(pos>wei){        ++ans;        return;    }    if(pos==1){        if(state){            rep(i,1,d[pos]){                w[pos]=i;                dfs(pos+1,i==d[pos]);            }        }else{            rep(i,1,9){                w[pos]=i;                dfs(pos+1,state);            }        }    }else{        if(state){            rep(i,1,d[pos]){                if(w[pos-1]%i==0){                    w[pos]=i;                    dfs(pos+1,i==d[pos]);                }            }        }else{            rep(i,1,9){                if(w[pos-1]%i==0){                    w[pos]=i;                    dfs(pos+1,state);                }            }        }    }}int main(){    cin>>T;    while(T--){        scanf("%d%d",&L,&R);        L--;        int tempL=L;        wei=calc(L);        rep2(i,wei,1){            d[i]=(L%10);            L/=10;        }        ans=0;        if(tempL==0){            ans=0;        }else{            dfs(1,true);        }        ans1=ans;        mem(dp,0);        rep(i,1,9) dp[1][i]=1;        rep(i,2,wei-1){            rep(j,1,9){                rep(k,1,9){                    if(j%k==0){                        dp[i][j]+=dp[i-1][k];                    }                }            }        }        rep(i,1,wei-1){            rep(j,1,9) ans1+=dp[i][j];        }        wei=calc(R);        rep2(i,wei,1){            d[i]=(R%10);            R/=10;        }        ans=0;        dfs(1,true);        ans2=ans;        mem(dp,0);        rep(i,1,9) dp[1][i]=1;        rep(i,2,wei-1){            rep(j,1,9){                rep(k,1,9){                    if(j%k==0){                        dp[i][j]+=dp[i-1][k];                    }                }            }        }        rep(i,1,wei-1){            rep(j,1,9) ans2+=dp[i][j];        }        printf("%d\n",ans2-ans1);    }    return 0;}