CodeForces 55D Beautiful numbers(디지털 dp&&이산화)

제목 링크: [kuangbin이 너를 데리고 날아간다] 주제 15자리 DP A - Beautiful numbers
제목의 뜻
ps: 첫 번째 디지털 dp, 문제 정말 좋아요. 큰 소의 방법을 참고하여 깨달았지만 a를 많이 얻었어요.
구간 내의 Beautiful numbers가 몇 개인지 구하세요.Beautiful numbers: 하나의 수로 구성된 모든 0이 아닌 숫자를 정제할 수 있습니다.예를 들어 15는 1과 5로 나누어질 수 있기 때문에 15는 Beautiful numbers이다.
사고의 방향
Beautiful numbers: 하나의 수로 구성된 모든 0이 아닌 숫자를 정제할 수 있습니다.하나의 수로 그것을 구성하는 모든 0이 아닌 숫자의 최소 공배수를 정제할 수 있는 것과 같다.우리가 본 데이터의 범위는 1 ≤  ≤  ≤ 9 ·1018로 기록할 수 없다.그래서 범위를 좁히는 것이 가장 중요한 일이다.먼저 작은 형식을 보아라.

    sum%(x*n)%x == sum%x;

  ： sum ＝ k*x+b
        :
        sum%(x*n)%x -> (k*x+b)%(x*n)%x 
         k  ka*n + kb  ;
        (ka*n*x+kb*x+b)%(x*n)%x -> (kb*x+b)%x -> b%x -> b
        :
        b
    ，    

그러면 우리는 상식 중의 x*n을 사용하여num에 대해 잉여를 취하고 그 잉여 후의 값을 기록할 수 있다. 분명히 1~9의 최소 공배수 2520이 가장 합리적인 x*n이다.한 자리씩 통계할 때, 앞자리에서 남은 값을 직접 뽑아서 새 자리를 포함하는 새 숫자에서 남은 값을 얻을 수 있다.예를 들어 RX(R는 앞자리를 알고 나머지를 얻은 값)라면 Rx%2520==(R*10+x)%2520.더 이상 쓸데없는 말은 하지 않겠습니다.우리는 기억화 검색을 사용합니다.**ffs(len,num,lcm,flag)len은 교체된 길이를 표시하고,num는 현재 위치의 수를 2520에서 얻은 값입니다.lcm는 현재 위치까지의 모든 수의 최소 공배수입니다.flag는 현재 수가 임의로 값을 받을 수 있는지 여부를 표시합니다. (값 상한선에 대한 판단) **는 dp[len] [num] [lcm]로 기록할 수 있습니다.그러나 lcm는 2520에 따라 값을 매길 수 없기 때문에 lcm를 이산화한다. lcm는 반드시 2520을 정제할 수 있기 때문에 1~2520은 2520을 정제할 수 있는 수를 표시하면 된다. 테스트 결과 48개만 발견되어 현재 상황을 만족시킬 수 있다.
코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

#define LL long long
const int MOD = 2520;
LL dp[20][50][2550];
int dis[20];
int Hash[2550];

LL gcd(LL a, LL b)
{
    return b?gcd(b,a%b):a;
}

LL dfs(int len, int num, int lcm, bool flag)
{
    if(-1==len) return num%lcm == 0;
    if(!flag && -1==dp[len][Hash[lcm]][num]) return dp[len][Hash[lcm]][num];
    LL ans = 0;
    int end = flag?dis[len]:9;
    for(int i=0; i<=end; i++)
        ans += dfs(len-1, (num*10+i)%MOD, i?lcm*i/gcd(lcm,i):lcm, flag&&i==end);
    if(!flag) dp[len][Hash[lcm]][num] = ans;
    return ans;
}

LL solve(LL n)
{
    int pos = 0;
    while(n)
    {
        dis[pos++] = n%10;
        n /= 10;
    }
    return dfs(pos-1, 0, 1, 1);
}

int main()
{
    int T;
    scanf("%d", &T);
    int cnt = 0;
    for(int i=1; i<=MOD; i++)
        if(MOD%i == 0)
            Hash[i] = cnt++;
    memset(dp, -1, sizeof(dp));
    while(T--)
    {
        long long l, r;
        scanf("%lld%lld", &l, &r);
        printf("%lld
", solve(r)-solve(l-1));
    }
    return 0;
}