一个数， 他的所有位上的数都可以被这个数整除， 求出范围内满足条件的数的个数。
dp[i][j][k], i表示第i位， j表示前几位的lcm是几， k表示这个数mod2520， 2520是1-9之间数的lcm。 然后这样数组就要开成20*2520*2520， 太大了， 所以我们将lcm离散， 因为1-9的lcm根本没有那么多的数， 实际上只有48个。
这题好难想...
#include<bits/stdc++.h>
using namespace std;
#define mem1(a) memset(a, -1, sizeof(a))
#define ll long long
int digit[], len, idx[];
ll dp[][][];
int gcd(int a, int b) {
return b==?a:gcd(b, a%b);
}
int get_lcm(int a, int b) {
return a/gcd(a, b)*b;
}
void init() {
int num = ;
for(int i = ; i<=; i++) {
if(%i==)
idx[i] = num++;
}
mem1(dp);
}
ll dfs(int len, int lcm, int num, int f) {
if(!len) {
return num%lcm==;
}
if(!f&&dp[len][num][idx[lcm]]!=-)
return dp[len][num][idx[lcm]];
ll ret = , maxx = f?digit[len]:;
for(int i = ; i<=maxx; i++) {
if(i == ) {
ret += dfs(len-, lcm, (num*)%, f&&i==maxx);
} else {
int tmp = get_lcm(lcm, i);
ret += dfs(len-, tmp, (num*+i)%, f&&i==maxx);
}
}
if(!f)
return dp[len][num][idx[lcm]] = ret;
return ret;
}
ll cal(ll n) {
len = ;
while(n) {
digit[++len] = n%;
n/=;
}
return dfs(len, , , );
}
int main()
{
ll a, b, t;
init();
cin>>t;
while(t--) {
scanf("%I64d%I64d", &a, &b);
printf("%I64d\n", cal(b)-cal(a-));
}
return ;
}