一个数， 他的所有位上的数都可以被这个数整除， 求出范围内满足条件的数的个数。
dp[i][j][k], i表示第i位， j表示前几位的lcm是几， k表示这个数mod2520， 2520是1-9之间数的lcm。 然后这样数组就要开成20*2520*2520， 太大了， 所以我们将lcm离散， 因为1-9的lcm根本没有那么多的数， 实际上只有48个。
这题好难想...
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mem1(a) memset(a, -1, sizeof(a)) 4 #define ll long long 5 int digit[30], len, idx[3000]; 6 ll dp[30][2522][50]; 7 int gcd(int a, int b) { 8 return b==0?a:gcd(b, a%b); 9 } 10 int get_lcm(int a, int b) { 11 return a/gcd(a, b)*b; 12 } 13 void init() { 14 int num = 0; 15 for(int i = 1; i<=2520; i++) { 16 if(2520%i==0) 17 idx[i] = num++; 18 } 19 mem1(dp); 20 } 21 ll dfs(int len, int lcm, int num, int f) { 22 if(!len) { 23 return num%lcm==0; 24 } 25 if(!f&&dp[len][num][idx[lcm]]!=-1) 26 return dp[len][num][idx[lcm]]; 27 ll ret = 0, maxx = f?digit[len]:9; 28 for(int i = 0; i<=maxx; i++) { 29 if(i == 0) { 30 ret += dfs(len-1, lcm, (num*10)%2520, f&&i==maxx); 31 } else { 32 int tmp = get_lcm(lcm, i); 33 ret += dfs(len-1, tmp, (num*10+i)%2520, f&&i==maxx); 34 } 35 } 36 if(!f) 37 return dp[len][num][idx[lcm]] = ret; 38 return ret; 39 } 40 ll cal(ll n) { 41 len = 0; 42 while(n) { 43 digit[++len] = n%10; 44 n/=10; 45 } 46 return dfs(len, 1, 0, 1); 47 } 48 int main() 49 { 50 ll a, b, t; 51 init(); 52 cin>>t; 53 while(t--) { 54 scanf("%I64d%I64d", &a, &b); 55 printf("%I64d ", cal(b)-cal(a-1)); 56 } 57 return 0; 58 }