思路：典型的数位DP！！！
dp[i][j][k]:第i位，对mod取余为j，数字和对mod取余为k。
注意：由于32位数字和小于95，所以当k>=95时，结果肯定为0.
这样数组就可以开小点，不会超内存！！
代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<vector> 6 #include<cstring> 7 using namespace std; 8 int dp[11][95][95],bit[11],k; 9 int dfs(int pos,int m,int s,bool f) 10 { 11 if(pos==-1) return !m&&!s; 12 if(!f&&dp[pos][m][s]!=-1) return dp[pos][m][s]; 13 int ans=0; 14 int e=f?bit[pos]:9; 15 for(int i=0;i<=e;i++){ 16 ans+=dfs(pos-1,(10*m+i)%k,(s+i)%k,f&&i==e); 17 } 18 if(!f) dp[pos][m][s]=ans; 19 return ans; 20 } 21 int cal(int n) 22 { 23 int m=0; 24 while(n){ 25 bit[m++]=n%10; 26 n/=10; 27 } 28 return dfs(m-1,0,0,1); 29 } 30 int main() 31 { 32 int t,ca=0,a,b,ans; 33 scanf("%d",&t); 34 while(t--){ 35 scanf("%d%d%d",&a,&b,&k); 36 memset(dp,-1,sizeof(dp)); 37 if(k>=95) ans=0; 38 else ans=cal(b)-cal(a-1); 39 printf("Case %d: %d ",++ca,ans); 40 } 41 return 0; 42 }