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]，记录在离散数组中的编号。

贴代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 const int mod = 2520;
 4 using namespace std;
 5 typedef long long int LL;
 6 template<typename T>T gcd(T a,T b)
 7 {
 8     return b==0?a:gcd(b,a%b);
 9 }
10 template<typename T>T lcm(T a,T b)
11 {
12     if(a*b == 0 ) return a?a:b;
13     return a/gcd(a,b)*b;
14 }
15 int  ra[mod+5];
16 int lm[50];
17 LL dp[22][50][mod+5];
18 int e[22];
19 int p[22];
20 void init()
21 {
22     e[0] =1;
23     for(int i=1; i<20; ++i)
24         e[i] = e[i-1]*10%mod; //e[i]表示10^i%2520的余数
25     int cnt=0;
26     for(int i=1; i<=mod; ++i)
27         if(mod%i == 0) lm[cnt] = i,ra[i] = cnt,++cnt;//记录2520的因子
28     //ra记录这个因子在离散化存因子中的编号
29 }
30 void onceInit()
31 {
32     init();
33     dp[0][0][0] = 1;
34     for(int i=1; i<20; ++i)
35     {
36         for(int t=0; t<10; ++t)
37         {
38             for(int j=0; j<48; ++j)
39             {
40                 int d = lcm(lm[j],t);
41                 int jj = ra[d];
42                 for(int k=0; k<2520; ++k)
43                 {
44                     int kk = (t*e[i-1]+k)%mod;
45                     dp[i][jj][kk] += dp[i-1][j][k];
46                 }
47             }
48         }
49     }
50 }
51 int splitInt(LL x)//将数拆成一位一位的存在ｐ数组中
52 {
53     int i;
54     for(i=1; x; ++i)
55         p[i] = x%10,x /= 10;
56     return i;
57 }
58 LL solve(LL x)//统计从0-x中有多少个beautiful number，x不包含在内
59 {
60     LL ans =0;
61     int len = splitInt(x);
62     int cu1=1,cu2=0;//前面数的公倍数，余数
63     for(int i=len-1; i> 0; --i)
64     {
65         for(int t=0; t<p[i]; ++t)
66         {
67             for(int j=0; j<48; ++j)
68             {
69                 int d = lcm(lm[j],t);
70                 d = lcm(d,cu1);//这是真正的公倍数
71                 int tmp = (cu2+t)*e[i-1]%d;//k+tmp = l*d这样的k会是解
72                 for(int k=(d-tmp)%d; k < 2520; k +=d)
73                     ans += dp[i-1][j][k];
74             }
75         }
76         cu1=lcm(cu1,p[i]);//更新前面的余数和倍数
77         cu2 = (cu2+p[i])*10%mod;
78     }
79     return ans;
80 }
81 int main()
82 {
83 //    freopen("in.c","r",stdin);
84     onceInit();
85     int t;
86     scanf("%d",&t);
87     while(t--)
88     {
89         LL a,b;
90         scanf("%I64d%I64d",&a,&b);
91         printf("%I64d
",solve(b+1) - solve(a));
92     }
93     return 0;
94 }

View Code