CF55D 아름 다운 숫자 (디지털 DP)

codeforces 55D 아름 다운 숫자 (디지털 DP)
원제 주소:http://codeforces.com/problemset/problem/55/D
D. Beautiful numbers
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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 ·1018).
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

제목 의 대 의 는 구간 [l, r] 내 에서 자신의 한 자릿수 로 나 눌 수 있 는 수가 얼마나 되 는 지 를 요구 하 는 것 이다.
분명히 디지털 DP 입 니 다.
디지털 DP 는 기억 화 된 검색 으로 해결 할 수 있 습 니 다.
요점 은 두 가지 가 있 는데 하 나 는 DP 배열 의 디자인 이 고 하 나 는 DFS 의 상태 디자인 이다.
자신 한 명 한 명 에 게 정 제 돼 야 한 다 는 점 을 감안 하면 한 자릿수 의 최소 공배수 에 의 해 정 제 될 수 있 는 것 과 같다.
계산 을 통 해 알 수 있 듯 이 1 ~ 9 의 최소 공배수 가 2520 이다.
DP 배열 의 디자인 은 보통 DP [자릿수] [최소 공배수] [mod 2520 의 나머지] 를 생각 합 니 다.
그러나 이렇게 되면 우 리 는 DP [20] [2520] [2520] [2520] 까지 배열 을 켜 야 한다. 그러면 반드시 메모리 가 터 질 것 이다.
1 ~ 9 의 서로 다른 조합의 최소 공배수 도 48 개 에 불과 하 다 는 점 을 고려 하면 DP 의 2 차원 을 48 로 낮 출 수 있다.
DFS 상 태 는 이전 한 분 당 최소 공배수 와 2 천 520 의 잔 수 를 기록 해 다음 층 에 보 내 도록 설계 할 수 있다.
따라서 DP [20] [48] [2520] 는 각각 숫자, 최소 공배수, 대 2520 의 여 수 를 나타 낸다.
long long int dfs (int pos, int lcm, int mod, bool limit) 는 각각 디지털, 최소 공배수, 2520 의 나머지, 경 계 를 처리 합 니 다.
그럼 저 희 는 일 을 시작 할 수 있 습 니 다.
궁 매 진 첩 ~ ↓

디지털 DP 는 몇 가지 주의해 야 할 부분 이 있 습 니 다. 저 는 이런 세부 사항 때문에 많은 고생 을 했 습 니 다. (하루 종일 BUG 를 찾 고 있 습 니 다)
여 가 를 구 할 때, 일반적으로 이렇게 구한다. 예 를 들 면.
1234%18
숫자 를 분리 해서 다음 사람 에 게 전달 해 야 하기 때문이다.
그래서 내 가 처음에 쓴 것 은:
(((1*10^3 % 18 + 2*10^2) % 18 + 3*10^1) %18 + 4*10^0)%18
최후 의 여 수 를 구하 다
그러나 이렇게 하면 pow 함 수 를 사용 하지 않 을 수 없습니다. pow 함수 의 오차 가 너무 커서 CF 에서 데이터 가 1000 에 이 르 렀 을 때 오차 가 발생 했 습 니 다. 네 번 째 샘플 은 이미 끊 겼 습 니 다.
밤새 BUG 를 찾 아 여러 가지 디 테 일 을 검 사 했 습 니 다. 마지막 으로 다음날 아침 pow 의 오차 가 생각 났 습 니 다.
그래서 손 으로 pow 함 수 를 썼 습 니 다. 제 생각 에는 괜 찮 을 것 같 습 니 다. 과연 4 조 의 사례 가 지나 서 5 조 에 걸 렸 습 니 다.
다 안 좋 은 것 같 아 요. T ^ T.
손 으로 쓴 pow 에 도 오차 가 있 으 니 사용 하지 않 을 수 밖 에 없습니다.
대신 코드 를 봤 어 요. 대신 은 pow 를 사용 하지 않 았 어 요.
그 는 이렇게 여 수 를 구 했다 ↓
1234%18
=（（（1%18）*10 + 2）%18*10 + 3）%18 *10 + 4）%18
이렇게 되면 한 번 에 10 을 곱 하기 만 하면 된다. pow 나 너무 많은 누적 승 을 할 필요 가 없다.
다음 코드 붙 이기:

#include
#include
#include
#include
#include
using namespace std;    
int lcms[2523];
long long int dp[20][48][2524];
int digit[20];
int gcd(int a,int b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
}


void init()
{
    int num=0;
    for(int i=1; i<=2520; i++)
        if(2520%i==0)
        {
            lcms[i]=num++;
        }
}
long long int dfs(int pos,int lcm,int mod,bool limit)
{
    if(pos==-1)
    {
        return mod%lcm==0;
    }
    if(!limit&&dp[pos][lcms[lcm]][mod]!=-1)
    {
        return dp[pos][lcms[lcm]][mod];
    }
    long long int res=0;
    int tmp=limit? digit[pos]:9;

    for(int i=0; i<=tmp; i++)
    {
        int Nmod=(mod*10+i)%2520;
        int Nlcm;
        if(i==0||i==1)
        {
            Nlcm=lcm;
        }
        else
        {
            Nlcm=lcm/gcd(lcm,i)*i;
        }
         res+=dfs(pos-1,Nlcm,Nmod,limit&&i==tmp);
    }
    if(!limit)
    {
        dp[pos][lcms[lcm]][mod]=res;
    }
    return res;
}
long long int cal(long long int a)
{
    int len=0;
    while(a)
    {
        digit[len++]=a%10;
        a=a/10;
    }
    return dfs(len-1,1,0,1);
}
int main()
{
    long long int t,a,b;
    scanf("%I64d",&t);
    memset(dp,-1,sizeof(dp));
    memset(lcms,-1,sizeof(lcms));
    init();
    while(t--)
    {
        scanf("%I64d%I64d",&a,&b);
        printf("%I64d
",cal(b)-cal(a-1));
    }
    return 0;
}