题意：数字满足的条件是该数字可以被它的每一位非零位整除。
分析：大概的思路我是可以想到的 ， 但没有想到原来可以这样极限的化简 ， 在数位dp 的道路上还很长呀 ；
我们都知道数位dp 的套路 ， 核心的部分就是找到判断这个数的满足条件的方法 ， 如果找到了那这个问题就迎刃而解了吧 ；
这个题的条件是数字被每一位非零的数整除，那是不是这个是应该被每一位的最小公倍数整除 ，这里是这道题目的关键！！！！！！！！ 1-9的最小公倍数是2520 ， 所以其他位数最公倍数都是在2520内的（看这样考虑的话 dp数组只要开2520就好了 ,牛逼！！！）
dfs( pos , num , lcm , limit) : 在第几位 ， 当前的数字，当前数字所有非零位的最小公倍数，是否限制。
下面关键的地方又来了： 因为我们枚举完判断是num%lcm是否为0 ， 所以！！每次传入num都%2520!! ,这样数组又可以开小了许多 ；
但是因为我们的dp[pos][num][lcm] , 19*2520*2520 , 这个是无法开的 ， 那我们这么办呢？？
又是一个关键！这里居然用到离散化 ！！ 牛逼！ 所以对于lcm这一维我们需要进行离散化，经过打表可以发现，2520内可以整除2520的只有48个，所以我们可以离散化一下让lcm映射到1-48既可以了这样就可以开19x2520x48大小的了。1-2520中可能是最小公倍数的其实只有48个，经过离散化处理后，dp数组的最后一维可以降到48，这样就不会超了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int MOD = 2520; int Hash[3000]; int digit[50]; ll dp[50][2530][50]; void init(){ int cnt = 0; for(int i = 1; i <= MOD; i++){ if(MOD % i == 0) Hash[i] = cnt++; } } ll gcd(ll a,ll b){ if(!b) return a; else return gcd(b,a%b); } ll dfs(int pos,int num,int lcm,int limit){ if(pos == -1) return num % lcm == 0; ll &dpnow = dp[pos][num][Hash[lcm]]; if(!limit && dpnow != -1) return dpnow; int max_digit = limit ? digit[pos] : 9; ll ans = 0; for(int i = 0; i <= max_digit; i++){ ans += dfs((pos - 1), ((num * 10 + i) % MOD), (!i ? lcm : lcm * i / gcd(lcm,i)), (limit && i == max_digit)); } if(!limit) dpnow = ans; return ans; } ll solve(ll n){ int pos = 0; while(n){ digit[pos++] = n % 10; n /= 10; } return dfs(pos-1,0,1,1); } int main(){ init(); int t; cin >> t; memset(dp,-1,sizeof(dp)); while(t--){ ll l,r; cin >> l >> r; cout << solve(r) - solve(l-1) << endl; } return 0; }