题目链接：https://codeforces.com/problemset/problem/55/D
题意：
Volodya 是一个古怪的男孩，他的品味与众不同。对他来说，一个正整数是 漂亮数 ，当且仅当它能够被自身的各非零数字整除。我们不必与之争辩，只需计算给定范围中有多少个漂亮数。
输入
输入的第一行包含了测试用例的数目 t (1 ≤ t ≤ 10)。接下来的 t 行，每行包含两个自然数 li 和 ri (1 ≤ li ≤ ri ≤ 9 ·1018)。
思路：如果sum % kx == 0, 那么sum % x == 0, 所以我们考虑每位数的lcm，只要能够整除lcm就能整除所有位上的数。1~9的lcm是2520， 我们在数位dp时记录一下当前的数，个位数的公倍数，dp[i][j][k] 就表示枚举i位，当前数各位lcm是j，当前数是k的方案数，边界就是k % j == 0时为1，剩下的就是模板稍微修改一下了，对了，由于并不是所有的lcm都是满足条件的，所以我们要提前筛一下，就是离散化一下。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; #define ls rt << 1 #define rs rt << 1|1 #define mid ((l + r) >> 1) #define lson l, mid, ls #define rson mid + 1, r, rs const int maxn = 22; const int mod = 2520; ll dp[maxn][50][2525]; int a[maxn], h[2525]; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll dfs(int pos, int lcm, int num, int limit) { if(pos == 0) return num % lcm == 0; if(!limit && dp[pos][h[lcm]][num] != -1) return dp[pos][h[lcm]][num]; int up = limit ? a[pos] : 9; ll ret = 0; for(int i = 0; i <= up; ++i) { ret += dfs(pos - 1, i ? i * lcm / gcd(i, lcm) : lcm, (num * 10 + i) % mod, limit && (i == up)); } if(!limit) dp[pos][h[lcm]][num] = ret; return ret; } ll slove(ll x) { int tot = 0; while(x) { a[++tot] = x % 10; x /= 10; } return dfs(tot, 1, 0, 1); } int main() { int cnt = 0; for(int i = 1; i <= mod; ++i) //离散化一下 if(mod % i == 0) h[i] = ++cnt; int t; scanf("%d", &t); memset(dp, -1, sizeof(dp)); //放在这里是为了以后的状态可以再利用 while(t--) { ll x, y; scanf("%lld%lld", &x, &y); ll ans = slove(y) - slove(x - 1); printf("%lld\n", ans); } return 0; }
