题意：
统计[a, b]中有多少个数字满足：自身是k的倍数，而且各个数字之和也是k的倍数。
分析：
详细分析见《训练之南》吧，=_=||
书上提出了一个模板的概念，有了模板我们就可以分块计算。
虽然书上定义f(x)表示不超过x的非负整数且满足条件的个数，但为了编码方便，代码中f(x)的含义为0~x-1中满足条件的个数。
这样最终所求为f(b+1) - f(a)
#include <bits/stdc++.h>
using namespace std; int MOD;
int pow_ten[];
int f[][][]; inline int mod(int n)
{ return ((n % MOD) + MOD) % MOD; } int F(int d, int m1, int m2)
{
if(d == ) return m1 == && m2 == ? : ;
int& ans = f[d][m1][m2];
if(ans >= ) return ans; ans = ;
for(int x = ; x <= ; x++)
ans += F(d-, mod(m1-x), mod(m2-x*pow_ten[d-]));
return ans;
} int sum(int n)
{
char digits[];
sprintf(digits, "%d", n);
int nd = strlen(digits); int base = ;
int sumd = ;
int ans = ;
for(int i = ; i < nd; i++)
{
int na = nd - i - ;
for(int d = ; d < digits[i] - ''; d++)
ans += F(na, mod(-sumd-d), mod(-base-d*pow_ten[na]));
sumd += digits[i] - '';
base += (digits[i] - '') * pow_ten[na];
}
return ans;
} int main()
{
//freopen("in.txt", "r", stdin); pow_ten[] = ;
for(int i = ; i <= ; i++) pow_ten[i] = pow_ten[i - ] * ; int T, a, b;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &a, &b, &MOD);
if(MOD > ) { puts(""); continue; }
memset(f, -, sizeof(f));
printf("%d\n", sum(b+) - sum(a));
} return ;
}
代码君