学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5179

这是BestCode上的题目，但是比赛时，只有思路，却写不出来，当然，对于我来讲，能够知道用Dp来做这种思路就是一大满足了。

赛后看题解，说是最多有1299个解，可以先打印出来。擦，当时我已经推出最多有1299个解了，可咋就没想到打印呢，反正解又不多！！

代码及详解：

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define LL __int64

using namespace std;

int ans[13000];//保存所有的解
vector<int> v[10];//用来保存1~9的素因数
vector<int> num[10][10];//对一个数，从右到左对每位数标号，则num[i][j]表示第i位数字为j时的所有解


int main(){
    //freopen("C:\\Documents and Settings\\All Users\\×ÀÃæ\\IN2.txt","r",stdin);
    for(int i=1;i<=9;i++)
        for(int j=1;j<=i;j++)
            if(i%j==0) v[i].push_back(j);//打印素因数
    for(int i=1;i<=9;i++){//枚举位数
        for(int j=1;j<=9;j++){//枚举每一位的数字
            if(i==1){num[i][j].push_back(j);continue;}//当位数为一时，j都是满足条件的解
            for(int k=0;k<v[j].size();k++){//枚举位数i的前一位的可能情况，比如i位为9，则i-1只能为1,3,和9
                int x=v[j][k];
                for(int t=0;t<num[i-1][x].size();t++){//把i位的数字j插入到满足条件i-1位的每个数中
                    int tmp=(int)pow(10.0,i-1.0)*j+num[i-1][x][t];
                    num[i][j].push_back(tmp);//记录i，j的所有解
                }
            }
        }
    }
    int cnt=0;
    for(int i=1;i<=9;i++)
        for(int j=1;j<=9;j++)
            for(int t=0;t<num[i][j].size();t++)
                ans[cnt++]=num[i][j][t];//用ans一个数组记录出所有解，便于区间查找
    int T;cin>>T;
    while(T--)
    {
        int L,R;
        cin>>L>>R;
        L=lower_bound(ans,ans+cnt,L)-upper_bound(ans,ans+cnt,R);//用二分查找找到L,R的地址，地址差即为个数解
        cout<<abs(L)<<endl;
    }
    return 0;
}