Category:数位DPCF
Article From:https://www.cnblogs.com/oi-forever/p/9125839.html

A given interval [L, R], to find the number of perfect numbers in the interval. (a number is a perfect number if and only if the number can be divided into non zero numbers on all its digits).

Conclusion: digits on digit only need to consider 2~9, so use a number.`1<<8`To indicate which numbers have appeared.
If a number is a multiple of all the digits, then it must be the multiple of its minimum common multiple, and all the minimum common multiplier is 2520, so the sum of the sum is directly to 2520.
`dp[l][cnt][sum]`，lFor numeric length, what is the number of CNT digits, sum is the number sum.
`dfs(int l,int cnt,int sum,bool sig)`，sigWhether it is a boundary or not.

```#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MOD = 2520;
#define int ll
ll dp[20][1 << 8][2520]; int t, dight[20], tot;

ll dfs(int l, int cnt, int sum, bool sig) {
if(l == 0) {
for (int i = 2; i <= 9; ++i) {
if((cnt & (1 << (i - 2))) && (sum % i != 0)) return 0;
} return 1;
}
if(!sig && dp[l][cnt][sum] != -1) return dp[l][cnt][sum];
int nex = (sig ?dight[l] :9); ll res = 0;
for (int i = 0; i <= nex; ++i) {
res += (i < 2) ?dfs(l - 1, cnt, (sum * 10 + i) % MOD, sig && (i == nex)) :dfs(l - 1, cnt | (1 << (i - 2)), (sum * 10 % MOD + i) % MOD, sig && (i == nex));
}
if(!sig) dp[l][cnt][sum] = res;
return res;
}
ll calc(int a) {
tot = 0;
while(a) {
dight[++tot] = a % 10; a /= 10;
}
return dfs(tot, 0, 0, true);
}
main() {
scanf("%lld", &t);
memset(dp, -1, sizeof dp);
while(t--) {
ll l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", calc(r) - calc(l - 1));
}
return 0;
}
```