UVA_11361
首先，因为各个数位上的数字之和是不会大于100（我没有精确计算）的，那么K给这么大其实是唬人的，就当成K是小于100即可，大于等于100的情况可以直接输出0。
我们不妨先计算出小于等于B中有多少是满足要求的，再计算出小于等于A-1中有多少满足要求的，两者做差即可。比如现在计算小于等于B中有多少是满足要求的，在计算的时候可以用f[i][j][k]表示递推到了左起第i位时，数位上数字和模K为j，数本身模K为k的数中小于B的数一共有多少个，接下来如果采用刷表法的话，会有两部分需要考虑，一部分是当前本来就比B小，那么第i+1位是什么都无所谓，直接将f[i][j][k]累加到对应的f[i+1][*][*]上即可，另一部分就是当前前i位和B的前i位都相等，那么只有第i+1位取比B的i+1位上的数子要小的数字才会生成1个新的比B小的数，这样令对应的f[i+1][*][*]都自加1即可。
#include<stdio.h> #include<string.h> typedef long long LL; int A, B, K, a[11], f[11][110][110]; LL solve(int limit) { int s1 = 0, s2 = 0; for(int i = 10; i >= 0; i --) a[i] = limit % 10, limit /= 10; memset(f, 0, sizeof(f)); for(int i = 0; i < 10; i ++) { s1 = (s1 + a[i]) % K, s2 = (s2 * 10 + a[i]) % K; for(int j = 0; j < K; j ++) for(int k = 0; k < K; k ++) for(int d = 0; d < 10; d ++) f[i + 1][(j + d) % K][(k * 10 + d) % K] += f[i][j][k]; for(int d = 0; d < a[i + 1]; d ++) ++ f[i + 1][(s1 + d) % K][(s2 * 10 + d) % K]; } LL ans = f[10][0][0]; if((s1 + a[10]) % K == 0 && (s2 * 10 + a[10]) % K == 0) ++ ans; return ans; } int main() { int t; scanf("%d", &t); while(t --) { scanf("%d%d%d", &A, &B, &K); if(K >= 100) printf("0\n"); else printf("%lld\n", solve(B) - solve(A - 1)); } return 0; }