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

Tabris

CSDN数学codeforces数论动态规划

发布于：2016年8月26日

次浏览

[原创]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{19}=2520;
想到每个数都是 19 中某些数字的 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;
}

本页文档最后更新于：2021年5月16日

CSDN

codeforces

numbers