思路与算法

同样用前缀函数F(x)做区间差。状态记录位置、当前数位和对N的余数以及tight；每加一位d，余数变为(rem+d)%N。填完时只在余数0计一次。前导0不改变数位和，所以无需另设开始标志。原文分别约束a,b但未写大小顺序；按闭区间集合定义，当a>b时区间为空，返回0。

正确性说明

余数状态在每个前缀后都等于其数字和模N，因此终态为0当且仅当整个数符合要求。逐位枚举与上界标志保证每个0至x的整数恰好被计一次，且无超上界路径。0的数位和是0，在两个前缀中同被计入而相消。若a>b，不存在同时满足a<=x<=b的整数，空区间计数0正确。

复杂度

计算状态O(LN)，每个试10个数码，时间O(LN10)。每次前缀查询还初始化固定11100=1100个缓存槽，完整开销为O(1100+LN10)，空间O(1100+L)，包括递归栈。最多10位，N在1至99。含0的前缀计数在最大上界可为2^31，超过signed32，使用long long。

易错点

条件是数位和模N为0，不是原数模N。N=1时区间内所有正数都满足；N大于最大可达数位和时可能没有任何正数。每个区间的N都可能不同，缓存必须重置。空区间输出0，不交换输入端点改变集合。独立答案先求精确数位和的多项式系数分布，再按前缀枚举统计，不复用余数状态递归。

参考代码（C++11）

#include <cstring>
#include <iostream>
#include <string>
using namespace std;
string digits;
int mod;
long long memo[11][100];
long long visit(int pos, int remainder, bool tight) {
    if (pos == (int)digits.size())
        return remainder == 0;
    if (!tight && memo[pos][remainder] >= 0)
        return memo[pos][remainder];
    int upper = tight ? digits[pos] - '0' : 9;
    long long ans = 0;
    for (int d = 0; d <= upper; ++d)
        ans += visit(pos + 1, (remainder + d) % mod, tight && d == upper);
    if (!tight)
        memo[pos][remainder] = ans;
    return ans;
}
long long count(long long x) {
    if (x < 0)
        return 0;
    digits = to_string(x);
    memset(memo, -1, sizeof(memo));
    return visit(0, 0, true);
}
int main() {
    long long a, b;
    while (cin >> a >> b >> mod) {
        if (a > b)
            cout << 0 << '\n';
        else
            cout << count(b) - count(a - 1) << '\n';
    }
}