作者:
炽热的
,
2023-03-16 19:31:47
,
所有人可见
,
阅读 30
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int len;
int nums[20], f[20][100][100];
int dfs(int pos, int mod, int val, int p, int limit) {
if (val < 0) return 0;
if (!pos) return !mod && !val;
if (!limit && ~f[pos][mod][val]) return f[pos][mod][val];
int up = limit ? nums[pos] : 9, res = 0;
for (int i = 0; i <= up; i ++ )
res += dfs(pos - 1, (mod * 10 + i) % p, val - i, p, limit && i == up);
return limit ? res : f[pos][mod][val] = res;
}
int calc(int x, int p) {
len = 0;
memset(f, -1, sizeof f);
while (x) nums[ ++ len] = x % 10, x /= 10;
return dfs(len, 0, p, p, 1);
}
int main() {
int l, r; cin >> l >> r;
int res = 0;
for (int i = 1; i <= 81; i ++ )
res += calc(r, i) - calc(l - 1, i);
cout << res;
return 0;
}