虽然依旧是套模板，但是因为我太弱了，不会建状态，所以去看了题解。。
这里就直接引用我看的题解吧，写的不错的。
题解
//我的代码
#include<cstdio>
#include<cstring>
using namespace std;
const int mod = 2520;
const int N = mod + 10;
typedef long long ll;
int a[20], lc[N], l;
ll f[20][N][50];
inline ll re()
{
ll x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
int gcd(int x, int y)
{
if (!y)
return x;
return gcd(y, x % y);
}
int LCM(int x, int y)
{
if (!y)
return x;
return x / gcd(x, y) * y;
}
ll dfs(int pos, int nw, int lcm, int lm)
{
if (pos < 0)
return nw % lcm ? 0 : 1;
if (!lm && f[pos][nw][lc[lcm]] > -1)
return f[pos][nw][lc[lcm]];
int i, k = lm ? a[pos] : 9;
ll s = 0;
for (i = 0; i <= k; i++)
s += dfs(pos - 1, (nw * 10 + i) % mod, LCM(lcm, i), lm && i == a[pos]);
if (!lm)
return f[pos][nw][lc[lcm]] = s;
return s;
}
ll calc(ll x)
{
int k = 0;
do
{
a[k++] = x % 10;
x /= 10;
} while (x > 0);
return dfs(k - 1, 0, 1, 1);
}
int main()
{
int i, t;
ll n, m;
for (i = 1; i * i <= mod; i++)
if (!(mod % i))
{
lc[mod / i] = ++l;
lc[i] = ++l;
}
memset(f, -1, sizeof(f));
t = re();
for (i = 1; i <= t; i++)
{
n = re();
m = re();
printf("%I64d\n", calc(m) - calc(n - 1));
}
return 0;
}Codeforces55D Beautiful numbers
原文：https://www.cnblogs.com/Iowa-Battleship/p/9712895.html