CF55D

传送门

简要题意

定义一个正整数为美丽的当且仅当这个数能被所有非零位上的数整除。
给定$l$,$r$，求$l$到$r$中有多少数是美丽的。
多组数据，$l,r\le 9\times 10^{18}$

简要题解

数位DP。
“美丽”的数要求被所有非零位上的数整除，也就是$2,3,4,...,9$这些数字如果出现了一定能整除这个数。
所以我们可以用$0..2^8-1$来记录每个数字的出现情况（是否出现）

要求被这些数整除，就相当于被它们的最小公倍数整除。

因为$LCM(2,3,4,...,9)=2520$，所以我们可以考虑这个数$\mod 2520$的值，如果这个值能被这些数位整除，那么原数一定能被这些数位整除。

设$dp[i][j][k]$表示计算到从低到高第$i$位，前面的数$\mod 2520 = j$，$2..9$的出现情况是$k$，并且不是边界情况的方案数。

利用记忆化搜索。
记$dfs(j,k,i,bj)$表示计算到从低到高第$i$位，前面的数$\mod 2520 = j$，$2..9$的出现情况是$k$,如果$bj=1$则是边界情况，否则不是的方案数。

详细写法见代码。
注意：

1. CF机子用的是windows，要用%I64d或cin/cout输入输出。
2. CF机子估计是32位的，尽量不要用long long，否则可能会TLE on Test 8

/*
Author: CNYALI_LK
LANG: C++
PROG: CF55D.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define aint(x) x.begin(),x.end()
#define end(...) {printf(__VA_ARGS__);exit(0);}
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int a[102],t;
ll dp[20][2560][300];
ll dfs(int md,int cx,int w,int bj){
    if(!bj&&dp[w][md][cx]+1)return dp[w][md][cx];
    if(w==0){
        for(int i=0;i<8;++i){
            if((cx&(1<<i))&&(md%(i+2))){
                return dp[w][md][cx]=0;
            }
        }
        return dp[w][md][cx]=1; 
    }
    if(bj){
        ll ans=0;
        for(int i=0;i<a[w];++i){
            if(i<2){
                ans+=dfs((md*10+i)%2520,cx,w-1,0);
            }
            else ans+=dfs((md*10+i)%2520,cx|(1<<(i-2)),w-1,0);
        }
        if(a[w]<2)ans+=dfs((md*10+a[w])%2520,cx,w-1,1);
        else ans+=dfs((md*10+a[w])%2520,cx|(1<<(a[w]-2)),w-1,1);
        return ans;
    }
    else{
        dp[w][md][cx]=0;
        for(int i=0;i<10;++i){
            if(i<2){
                dp[w][md][cx]+=dfs((md*10+i)%2520,cx,w-1,0);
            }
            else dp[w][md][cx]+=dfs((md*10+i)%2520,cx|(1<<(i-2)),w-1,0);
        }
        return dp[w][md][cx]; 

    }
}
ll f(ll x){
    t=0;
    while(x){
        a[++t]=x%10;
        x/=10;
    }
    return dfs(0,0,t,1);
}
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ll t,l,r;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    while(t){
        --t;
        cin>>l>>r;
        cout<<f(r)-f(l-1)<<endl;
    }
    return 0;
}