51nod 1232：完美数

题目链接：

题目大意：如果一个数能够被组成它的各个非$0$数字整除，则称它是完美数。例如：$10$,$11$,$12$,$101$都是完美数，但是$13$就不是完美数（因为$13$不能被数字3整除）。现在给定正整数$x$,$y$，求$[x,y]$中共有多少完美数。共有$T$组数据。

数位DP

如果对于$a \equiv r(mod m)$，存在$p|m$，则有$a \equiv r(mod p)$.

故我们可以记录被$2520$（$lcm(1,2,3,4,5,6,7,8,9)$）模的余，代替分别记录被$1,2,3,4,5,6,7,8,9$模的余.

而标识$n$中含哪些数有多种方法：可以记录$lcm(p_i)$（此种需将$2520$的因子离散化），也可以用多个bool类型标记.

由于这道题$T$过大，故递推的方法不可行，采用记忆化搜索.

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #define N 20 6 using namespace std; 7 typedef long long ll; 8 const int m=2520; 9 int T,dig[N];10 ll a,b,dp[N][50][2520],f[2525],g[50],mod[20];11 int gcd(int a,int b){12     return b==0?a:gcd(b,a%b);13 }14 int lcm(int a,int b){15     return a/gcd(a,b)*b;16 }17 ll dfs(int pos,int fact,int r,bool limit){18     if (pos<0) return r%g[fact]==0;19     if (!limit&&dp[pos][fact][r]!=-1) return dp[pos][fact][r];20     ll res=0;21     int last=limit?dig[pos]:9;22     for (int i=0;i<=last;i++){23         int x=g[fact];24         if(i>1)x=lcm(x,i);25         res+=dfs(pos-1,f[x],(r+mod[pos]*i)%m,limit&&(i==last));26     }27     if (!limit) dp[pos][fact][r]=res;28     return res;29 }30 ll solve(ll n){31     int len=0;32     while (n){33         dig[len++]=n%10;34         n/=10;35     }36     return dfs(len-1,0,0,1);37 }38 void init(){39     int k=0,i;40     memset(dp,-1,sizeof(dp));41     for(i=1;i*i