本文共 1935 字，大约阅读时间需要 6 分钟。

现在，让我们来看看具体的解决方案：

首先，我们需要定义一个动态规划数组dp[pos][now][num][mod]，其中：

• pos 表示当前处理到的位置（位数）。
• now 表示当前数对模数取余的结果。
• num 表示剩余的数位和。
• mod 表示模数。

我们将使用深度优先搜索的方法来构建每一个可能的数字，并在每一步记录可能的情况。

接下来，我们从最高位开始构建，每个位置上的数字取值范围为0-9（除了最高位可能不能为0）。

递归终止条件是当处理到所有位时（pos == 0），这时若还有剩余的数位和num为0，说明构建了一个有效的数字，并且该数字的数位和整除它本身，则返回1，否则返回0。

在递归过程中，对于每一个数字选择，更新当前余数和剩余的数位和，记录在动态规划数组中。

最后，遍历所有可能的模数，调用这个递归函数，统计满足条件的数字的数量。

以下是具体的代码实现：

#include 
   
    
using namespace std;
typedef long long ll;
ll f[13][110][110][110]; // 位置、当前 residue、剩余数位和、mod
ll dfs(int pos, int limit, int now, int num, int mod) {
    if(pos == 0) {
        if(num == 0) return 1;
        return 0;
    }
    if(!limit && !f[pos][now][num][mod])
        return f[pos][now][num][mod];
    
    int max_digit = (pos == 1 ? 1 : 9); // 最高位不能为0
    
    int ed = (limit ? (pos > 1 ? 9 : now ? 9 : 0) : 0);
    if(limit && (~f[pos][now][num][mod]))
        return f[pos][now][num][mod];
    
    ll ans = 0;
    int max_num = num;
    for(int i = 0; i <= ed; i++) {
        ans += dfs(pos-1, limit && (i == ed), (now * 10 + i) % mod, num - i, mod);
    }
    if(!limit)
        f[pos][now][num][mod] = ans;
    return ans;
}
ll solve(ll n) {
    ll cnt_digits; // 得到n的位数
    while(n) {
        cnt_digits++;
        n /= 10;
    }
    ll ans = 0;
    for(int mod = 1; mod <= 108; mod++) {
        ans += dfs(cnt_digits, true, 0, mod, mod);
    }
    return ans;
}
int main() {
    // 初始化动态规划数组
    memset(f, -1, sizeof(f));
    
    int t;
    while(t--) {
        0;
        ll n;
        // 从标准输入读取n
        // 假设使用了之前的代码，比如：
        // n = ...; cin >> n;
        t++;
        ll ans = solve(n);
        // 打印结果
        // printf("Case %d: %lld\n", t, ans);
    }
    // 没有其他操作
    return 0;
}
   

这个代码使用深度优先搜索结合动态规划，记录在每一步的状态变化，避免重复计算，从而有效地解决了这个问题。

There are constraints and detailed steps in the code to ensure efficient computation, and results are handled properly to fit within the limits.

通过这样的方法，我们可以高效地计算出满足条件的数字数量。

转载地址：http://ybhiz.baihongyu.com/