Beautiful numbers [CF#51 D]

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

//dp[i][j][k] 表示长度为i的，对2520取模为j的，最小公倍数为k的数的个数，1~9最小公倍数只有48个，预处理出来。
const int MM = 11111;
typedef __int64 int64;
#define mod 2520
#define debug puts("wrong")
int64 N,L,R;
int num[MM],cnt;
int64 dp[19][2520][50];
int id[MM], g;

void get_init() {
    g=0;
    for(int i=1;i<=mod;i++) {
        if(mod%i==0) id[i]=g++;
    } 
}
int gcd(int x,int y) {
    int64 tmp;
    while(y) {
        tmp=y;
        y=x%y;
        x=tmp;
    }
    return x;
}

int lcm(int x,int y) { return x/gcd(x,y)*y; }

void get_data() {
    int i,j,k;
    scanf("%I64d%I64d",&L,&R);
}

int64 dfs(int le,int sum,int r,bool less) {
    if(le==-1) return sum%r==0;
    if(!less && dp[le][sum][id[r]]!=-1) return dp[le][sum][id[r]];
    int64 res=0; int d,e=less?num[le]:9,ss,rr;
    for(d=0;d<=e;d++) {
        ss=(sum*10+d)%mod;
        rr=r;
        if(d) rr=lcm(r,d);
        res+=dfs(le-1,ss,rr,less&&d==e);
    }
    if(!less) dp[le][sum][id[r]]=res;
    return res;
}

int64 cal(int64 x) {
    for(cnt=0; x ;num[cnt++]=x%10,x/=10);
    return dfs(cnt-1,0,1,true);
}

void solve() {
    int i,j,k;
    printf("%I64d\n",cal(R)-cal(L-1));
}
int main() {
    get_init();
    memset(dp,-1,sizeof(dp));
    int ca; scanf("%d",&ca);
    while(ca--) get_data(),solve();
    return 0;
}