An integer is divisible by 3 if the sum of its digits is also divisible by 3. For example, 3702 is divisible by 3 and 12 (3+7+0+2) is also divisible by 3. This property also holds for the integer 9.
In this problem, we will investigate this property for other integers.
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.
Each case contains three positive integers A, B and K (1 ≤ A ≤ B < 231 and 0 < K < 10000).
Output
For each case, output the case number and the number of integers in the range [A, B] which are divisible by K and the sum of its digits is also divisible by K.
Sample Input
3
1 20 1
1 20 2
1 1000 4
Sample Output
Case 1: 20
Case 2: 5
Case 3: 64
题解：dp[ pos ][ res1 ][ res2 ]表示当前位置，数位之和模K的余数，这些数位组成的数模K的余数。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 const int INF=0x3f3f3f3f; 8 9 int L,R,K; 10 int t[10],num[10],dp[10][90][90]; 11 12 void Inite(){ 13 t[0]=1; 14 for(int i=1;i<10;i++) t[i]=t[i-1]*10; 15 } 16 17 int DFS(int pos,int res1,int res2,bool F){ 18 if(pos==-1){ 19 if(res1==0&&res2==0) return 1; 20 else return 0; 21 } 22 23 if(!F&&dp[pos][res1][res2]!=INF) return dp[pos][res1][res2]; 24 int maxv=F?num[pos]:9; 25 26 int ans=0; 27 for(int i=0;i<=maxv;i++){ 28 int x=(res1+i*t[pos])%K; 29 int y=(res2+i)%K; 30 ans=ans+DFS(pos-1,x,y,(F&&i==maxv)?true:false); 31 } 32 33 if(!F) dp[pos][res1][res2]=ans; 34 return ans; 35 } 36 37 int Solve(int temp){ 38 if(temp==0) return 1; 39 int cnt=0; 40 while(temp){ 41 num[cnt++]=temp%10; 42 temp/=10; 43 } 44 return DFS(cnt-1,0,0,true); 45 } 46 47 int main() 48 { Inite(); 49 50 int kase; 51 cin>>kase; 52 for(int k=1;k<=kase;k++){ 53 cin>>L>>R>>K; 54 memset(dp,0x3f,sizeof(dp)); 55 56 int ans; 57 if(K>82) ans=0; 58 else ans=Solve(R)-Solve(L-1); 59 printf("Case %d: %d\n",k,ans); 60 } 61 return 0; 62 }
原文：http://www.cnblogs.com/zgglj-com/p/7518028.html