[原创]codeforces 55D beautiful number [数学+数位DP]【动态规划+数论】

2016-08-26 23:24:05 Tabris_ 阅读数：1697

博客爬取于2020-06-14 22:43:38
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52332586

题目连接 : http://codeforces.com/problemset/problem/55/D
-------------------------------.
D. Beautiful numbers
time limit per test4 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful numbers in given ranges.

Input
The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two natural numbers li and ri (1 ≤ li ≤ ri ≤ 9 ·10^18).

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Output
Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from li to ri, inclusively).

Examples
input
1
1 9
output
9
input
1
12 15
output
2
---------------------------------.

题目大意 :
就是求区间内能被所有位上的数字(!0)整除的数的个数

解题思路 ：

困了 明天再写吧，，
首先这很明显是一个数位DP
满足被所有位上的数字(!0)整除的数 其实就是满足被这些位数的lcm整除
然后就是怎么处理一个数在不断变化中 还要对lcm{xi}取模呢
这时候就要仔细思索其中的奥妙 也是本题最重要的一点.
首先lcm{1~9}=2520;
想到每个数都是1~9中某些数字的lcm 所以他们一定能整除2520

因为 若a≡b(mod m) 且d|m 则a≡b(mod d);
转化一下设b已经是对m取完模的了
于是得到 若a % m=b%m 且d|m 则a % d = b%d;
因为 **b=b%m ** 所以 b=b%m=b%d
所以 b%m%m=b%d%m
所以 b%m=b%d(km)%m

所以可以得到下 x%km%m<=>x%m

综上所述 x%2520%lcm{xi}==0 ; 是满足条件
而x%2520 是可以确定的 和大数取模类似
mod = (mod*10+本位数字)%2520 ;

所以我们开数组的时候要有x%2520 和lcm{xi}这两项 再加上位数 所以 数组应该这么开
dp[位数][x%2520][lcm{xi}];

但是这么开的话是这样的 dp[19][2520][2520] 1925202520 = 120657600 即使CF提供的256M的内存也会炸的不要不要的
所以得想办法优化一下

然后就想啊想 终于~~
想到每个数只能是1~9的最小公倍数 所以计算了下 所有的lcm一共有48种可 能 如下:
1 2 3 4 5 6 7 8 9 10 12 14 15 18 20 21 24 28 30 35 36 40 42 45 56 60 63 70 72 84 90 105 120 126 140 168 180 210 252 280 315 360 420 504 630 840 1260 2520
共计48种
然后就可以离散化一下 这样 dp[19][2520][2520]–>dp[19][2520][48]; 降低了空间复杂度 就可以AC了;

其实还可以继续优化 因为上面的结论 所以 %2520 <=>%252的 所以最后的数组可以优化到dp[19][252][48];
这样的时空复杂度均能得到下降
大家可以自己试一试

附本题代码
------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
# include <bits/stdc++.h>
using namespace std;
# define lalal puts("*****");

typedef long long LL;
const int MOD  = 1000000007;
const int maxn = 200010;

int  num[30],len;
LL  dp[30][2550][50];
int a[50],has[2520];

//x%2520%lcm == 0
int gcd(int a,int b)
{
    if(!b) return a;
    else return gcd(b,a%b);
}

int llcm(int a,int b)
{
    return a/gcd(a,b)*b;
}



LL dfs(int pos,int mod,int lcm,int limit)
{

    if(pos<0) return mod%lcm==0;

    if(!limit&&dp[pos][mod][has[lcm]]!=-1)
        {
  //          lalal;
            return dp[pos][mod][has[lcm]];
        }


    int endi = 9;
    if(limit) endi = num[pos];

    LL res = 0;
    int tlcm ;
    for(int i=0; i<=endi; i++)
    {
        if(!i) tlcm = lcm;
        else   tlcm = llcm(lcm,i);
        res += dfs(pos-1,(mod*10+i)%2520,tlcm,limit&&(i==endi));
    }

    if(!limit) dp[pos][mod][has[lcm]] = res;
    return res;
}

LL solve(LL n)
{
    len = 0;

    while(n)
    {
        num[len++] = n%10;
        n /= 10;
    }

    return dfs(len-1,0,1,1);
}

void init()
{
    memset(has,0,sizeof(has));
    int tem ;
    for(int i=0;i<(1<<9);i++)
    {
        tem = 1;
        for(int j=1;j<=9;j++)
        {
            if(i&(1<<j))
                tem = llcm(tem,j+1);
        }
        has[tem]=1;
    }

    int l = 0;
    for(int i=0;i<=2520;i++)
        if(has[i]) a[l]=i,has[i]=l++;

/*
    for(int i=0;i<l;i++)  printf("%d %d\n",has[a[i]],a[i]);
    puts("");
    printf("%d\n",l);
*/

}

int main()
{
   // printf("%d\n",2520*2520);
   init();
    memset(dp,-1,sizeof(dp));

    int _;
    scanf("%d",&_);
    while(_--)
    {
        LL n,m;
        scanf("%I64d%I64d",&m,&n);
        //cout <<n<<"  "<<m<<endl;
        // printf("%I64d %I64d\n",solve(n),solve(m-1));

        printf("%I64d\n",solve(n)-solve(m-1));
    }
    return 0;
}