1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int dp[10][82][82][82]; 5 int digit[10]; 6 int dfs(int p,int mod,int s,int m,bool e) { //位置，模数，前面之和，当前位数%mod，任意填 7  8     if (p==-1) return s==mod&&m==0; 9     if (!e &&dp[p][mod][s][m]!=-1) return dp[p][mod][s][m];10     int res = 0;11     int u = e?digit[p]:9;12     for (int d=0;d<=u;++d)13     {14         //printf("%d %d %d %d %d\n",p,mod,s,m,e);15         res+=dfs(p-1,mod,s+d,(m*10+d)%mod,e&&d==u);16     }17     return e?res:dp[p][mod][s][m]=res;18 }19 int solve(int n)20 {21     int len=0;22     while(n)23     {24         digit[len++]=n%10;25         n/=10;26     }27     int ans=0;28     for(int i=1;i<=81;i++)29     {30         ans+=dfs(len-1,i,0,0,1);31     }32     return ans;33 }34 int main()35 {36     int t;37     int n,m;38     //freopen("1.in","r",stdin);39     memset(dp,-1,sizeof(dp));40     scanf("%d",&t);41     for(int i=1;i<=t;i++)42     {43         scanf("%d%d",&n,&m);44         printf("Case %d: %d\n",i,solve(m)-solve(n-1));45     }46 }