CodeForces 55D Beautiful numbers(디지털 DP+ 상태 단순화, 레벨 5)

J - Beautiful numbers
Crawling in process...
Crawling failed
Time Limit:4000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u
Submit
Status
Appoint description: System Crawler (2012-05-31)
Description
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).
Sample Input
Input

1
1 9

Output

9

Input

1
12 15

Output

2

사고방식: 3차원 DP dp[몇 위][모형 최소 공배수의 여수][최소 공배수]
최소 공배수가 2520까지 되기 때문에 19x2520x2520폭의 공간이 필요합니다.
그러나 실제로 얻을 수 있는 최소 공배수는 2520개, 수십 개밖에 없기 때문에 DP는 다른 상태만 기록하면 되기 때문이다.
dp는 모든 수를 계산할 필요가 없습니다. 왜냐하면 서로 다른 수의mod수가 다르기 때문입니다.그래서 틀리지 않아요.
다음은 물 디지털 DP입니다.
     

#include<iostream>
#include<cstring>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
typedef long long LL;
using namespace std;
LL dp[22][2521][50];
const int MOD=2520;
int bit[22];
int gcd(int a,int b)
{ int z;
  while(b)
  {
    z=b;b=a%b;a=z;
  }
  return a;
}
int LCM(int a,int b)
{
  return a*b/gcd(a,b);
}
int to[2521];
void data()
{ int pos=0;
  FOR(i,1,2520)
  if(MOD%i==0)//       ,     
  {
    to[i]=pos++;
  }
}
LL DP(int pp,int mod,int lcm,bool big)
{
  if(pp==0)return mod%lcm==0;
  if(big&&dp[pp][mod][to[lcm]]!=-1)return dp[pp][mod][ to[lcm] ];
  int kn=big?9:bit[pp];
  LL ret=0;
  FOR(i,0,kn)
  { int zlcm;
    if(i==0)zlcm=lcm;
    else zlcm=LCM(lcm,i);
    ret+=DP(pp-1,(mod*10+i)%MOD,zlcm,big||kn!=i);
  }
  if(big)dp[pp][mod][to[lcm]]=ret;
  return ret;
}
LL get(LL x)
{
  int pos=0;
  while(x)
  {
    bit[++pos]=x%10;
    x/=10;
  }
  return DP(pos,0,1,0);
}
int main()
{
  LL x,y;data();clr(dp,-1);
  int n;
  cin>>n;
  while(n--)
  { cin>>x>>y;
    cout<<get(y)-get(x-1)<<"
";
  }
}