beautiful number 数位DP codeforces 55D

题目链接：

http://codeforces.com/problemset/problem/55/D

数位DP

题目描述：

一个数能被它每位上的数字整除（0除外），那么它就是beautiful number。问区间[a,b]上有多少个beautiful number。如102就是一个beautiful number，因为它能整除1,2。14不是，因为14不能整除4.

解法：

数位DP，设dp[i][j][k]为累计到第i为，公倍数为j，模lcm(1,2,```,9)=2520的余数为k的数的个数。注意到两个事实，要求某个数能整除它的每一个非0位上的数字，那么等价于将这些数字求一个最小公倍数，如果这个数能整除它的最小公倍数，自然就是beautiful number。已知lcm（1,2，···，9） = 2520，一个数一定能写成k+2520*x这样的形式，其中0<k<2520。设组成这个数的非0数字的最小公倍数为j,就有（k+2520*x）%j = k%j.同时能知道2520的因子（不一定是素数因子）一共有48个，所以离散的存储这些数，同时用ra[i]，记录在离散数组中的编号。

贴代码：

 #include <cstdio>

 #include <cstring>

 const int mod = ;

 using namespace std;

 typedef long long int LL;

 template<typename T>T gcd(T a,T b)

 {

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

 }

 template<typename T>T lcm(T a,T b)

 {

     if(a*b ==  ) return a?a:b;

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

 }

 int  ra[mod+];

 int lm[];

 LL dp[][][mod+];

 int e[];

 int p[];

 void init()

 {

     e[] =;

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

         e[i] = e[i-]*%mod; //e[i]表示10^i%2520的余数

     int cnt=;

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

         if(mod%i == ) lm[cnt] = i,ra[i] = cnt,++cnt;//记录2520的因子

     //ra记录这个因子在离散化存因子中的编号

 }

 void onceInit()

 {

     init();

     dp[][][] = ;

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

     {

         for(int t=; t<; ++t)

         {

             for(int j=; j<; ++j)

             {

                 int d = lcm(lm[j],t);

                 int jj = ra[d];

                 for(int k=; k<; ++k)

                 {

                     int kk = (t*e[i-]+k)%mod;

                     dp[i][jj][kk] += dp[i-][j][k];

                 }

             }

         }

     }

 }

 int splitInt(LL x)//将数拆成一位一位的存在ｐ数组中

 {

     int i;

     for(i=; x; ++i)

         p[i] = x%,x /= ;

     return i;

 }

 LL solve(LL x)//统计从0-x中有多少个beautiful number，x不包含在内

 {

     LL ans =;

     int len = splitInt(x);

     int cu1=,cu2=;//前面数的公倍数，余数

     for(int i=len-; i> ; --i)

     {

         for(int t=; t<p[i]; ++t)

         {

             for(int j=; j<; ++j)

             {

                 int d = lcm(lm[j],t);

                 d = lcm(d,cu1);//这是真正的公倍数

                 int tmp = (cu2+t)*e[i-]%d;//k+tmp = l*d这样的k会是解

                 for(int k=(d-tmp)%d; k < ; k +=d)

                     ans += dp[i-][j][k];

             }

         }

         cu1=lcm(cu1,p[i]);//更新前面的余数和倍数

         cu2 = (cu2+p[i])*%mod;

     }

     return ans;

 }

 int main()

 {

 //    freopen("in.c","r",stdin);

     onceInit();

     int t;

     scanf("%d",&t);

     while(t--)

     {

         LL a,b;

         scanf("%I64d%I64d",&a,&b);

         printf("%I64d\n",solve(b+) - solve(a));

     }

     return ;

 }