AcWing 1084. 数字游戏 II
原题链接
中等
作者:
炽热的
,
2023-03-15 09:50:04
,
所有人可见
,
阅读 137
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int len;
int nums[N], f[N][110];
int dfs(int pos, int sum, int p, int limit) {
if (!pos) return sum % p == 0;
if (!limit && ~f[pos][sum]) return f[pos][sum];
int up = limit ? nums[pos] : 9, res = 0;
for (int i = 0; i <= up; i ++ )
res += dfs(pos - 1, sum + i, p, limit && i == up);
return limit ? res : f[pos][sum] = 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, 1);
}
int main() {
int l, r, p;
while (cin >> l >> r >> p)
cout << calc(r, p) - calc(l - 1, p) << endl;
return 0;
}