cf 55D 数位dp 好题

/*
刚开始我考虑0的情况，想将他剔除就将lcmn设为-1，这样还要判断0和lcmn是-1的情况很麻烦而且但是一直出错
后来觉得不用管0的情况就行了，可以认为符合。
解：将lcmn离散化，因为1-9的公倍数必是2520的因子并且只有48个
所以用一个数组离散化，记忆的时候直接调用离散数组即可
因为一个数的所有数字的最小公倍数必定是2520的因子，所以将这个数对2520取余缩小范围并记忆
三维，第一个长度，第二个对2520取余，第三个是lcm值
*/
#include<stdio.h>
#include<string.h>
#define ll  __int64
ll dp[20][2600][50];
ll fp[2600];
ll digit[20];
ll gcd(ll a,ll b) {
if(b==0)return a;
return gcd(b,a%b);
}
ll dfs(ll len,ll mod,ll lcmn,ll ok) {
    if(!len) return mod%lcmn==0;
    if(!ok&&dp[len][mod][fp[lcmn]]!=-1)
        return dp[len][mod][fp[lcmn]];
    ll i,ans=0,maxx=ok?digit[len]:9;
    for(i=0;i<=maxx;i++) {
     if(i==0)
        ans+=dfs(len-1,(mod*10+i)%2520,lcmn,ok&&i==maxx);//如果是0的话就跳过
    else
        ans+=dfs(len-1,(mod*10+i)%2520,lcmn*i/gcd(lcmn,i),ok&&i==maxx);//求lcmn和和
    }
    if(!ok)
        dp[len][mod][fp[lcmn]]=ans;
    return ans;
}
ll f(ll n) {
ll len=0;
while(n) {
    digit[++len]=n%10;
    n/=10;
}
return dfs(len,0,1,1);
}
int main() {
    ll n,m,i,k,t;
    k=0;
    for(i=1;i<=2520;i++)
    if(2520%i==0)
     fp[i]=++k;//离散化
   // prllf("%d
",k);
    memset(dp,-1,sizeof(dp));
    scanf("%I64d",&t);
    while(t--) {
         scanf("%I64d%I64d",&n,&m);
        printf("%I64d
",f(m)-f(n-1));
    }
return 0;}