CF D. Beautiful numbers （数位dp）

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

Beautiful Numbers : 这个数能整除它的全部位上非零整数。问[l,r]之间的Beautiful Numbers的个数。

若一个数能整除它的全部的非零数位。那么相当于它能整除个位数的最小公倍数。

因此记忆化搜索中的參数除了len(当前位)和up（是否达到上界），有一个prelcm表示前面的数的最小公倍数。推断这个数是否是Beautiful Numbers，还要有一个參数表示前面数，可是这个数太大，须要缩小它的范围。

难点：

缩小前面组成的数的范围。

能够发现全部个位数的最小公倍数是2520，如果当前的Beautiful Numbers是x，

那么 x % lcm{dig[i]} = 0, 

又 2520%lcm{dig[i]} = 0，

那么x%2520%lcm{ dig[i] } = 0，x范围由9*10^18变为2520。

处理超内存问题。

经过分析后能够设出dp[20][2050][2050]，dp[i][j][k]表示处理到i位，前面的数的最小公倍数为j。前面的数%2520为k。

但这样

明显会TLE。。

由于1~9组成的最小公倍数仅仅有48个，能够离散化，这样数组就降到了dp[20][50][2520]。

#include <stdio.h>

#include <iostream>

#include <map>

#include <set>

#include <list>

#include <stack>

#include <vector>

#include <math.h>

#include <string.h>

#include <queue>

#include <string>

#include <stdlib.h>

#include <algorithm>

//#define LL __int64

#define LL long long

#define eps 1e-12

#define PI acos(-1.0)

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 4010;

const int max_lcm = 2520;

LL gcd(LL a, LL b)

{

    if(b == 0)

        return a;

    return gcd(b,a%b);

}

LL lcm(LL a, LL b)

{

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

}

int dig[25];

LL dp[25][50][2525];

int hash[2525];

LL dfs(int len, int prelcm, int prenum, int up)

{

    if(len == 0)

    {

        return prenum%prelcm == 0;

    }

    if(!up && dp[len][hash[prelcm]][prenum] != -1)

        return dp[len][hash[prelcm]][prenum];

    int n = up ?

dig[len] : 9;

    LL res = 0;

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

    {

        int nownum = (prenum*10+i)%max_lcm;

        int nowlcm = prelcm;

        if(i)

            nowlcm = lcm(prelcm,i);

        res += dfs(len-1,nowlcm,nownum,up&&i==n);

    }

    if(!up)

        dp[len][hash[prelcm]][prenum] = res;

    return res;

}

LL cal(LL num)

{

    int len = 0;

    while(num)

    {

        dig[++len] = num%10;

        num /= 10;

    }

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

}

int main()

{

    int test;

    LL a,b;

    int cnt = 0;

    for(int i = 1; i <= 2520; i++) //离散化

    {

        if(max_lcm % i == 0)

            hash[i] = ++cnt;

    }

    scanf("%d",&test);

    memset(dp,-1,sizeof(dp));

    for(int item = 1; item <= test; item++)

    {

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

        printf("%I64d\n",cal(b) - cal(a-1));

    }

    return 0;

}