1 /* 2 查询一段区间，有多少能被它各个数位之和整除的个数 3 */ 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 using namespace std; 8  9 int dp[11][82][82][82];//分别表示第i位,前缀数字各个和j,模k,余x10 int digit[11];11 12 int dfs(int pos,int sum,int mod,int res,int limit)13 {14     if(pos<=0) return mod==sum && res==0;//数字各个位之和一致且模mod为015     if(sum>mod) return 0;//若前缀各个位之和大于mod,则不符合条件了16     if(!limit && dp[pos][sum][mod][res]!=-1)17         return dp[pos][sum][mod][res];18     int ans=0;19     int end=limit?digit[pos]:9;20     for(int i=0;i<=end;i++)21         ans+=dfs(pos-1,sum+i,mod,(res*10+i)%mod,limit&&(i==end));22     if(!limit) dp[pos][sum][mod][res]=ans;23     return ans;24 }25 int solve(int n)26 {27     int pos=0;28     while(n)29     {30         digit[++pos]=n%10;31         n/=10;32     }33     int ans=0;34     for(int i=1;i<=81;i++)//枚举mod的值35         ans+=dfs(pos,0,i,0,1);36     return ans;37 }38 int main()39 {40     memset(dp,-1,sizeof(dp));41     int t,icase=0,a,b;42     scanf("%d",&t);43     while(t--)44     {45         scanf("%d%d",&a,&b);46         printf("Case %d: %d\n",++icase,solve(b)-solve(a-1));47     }48     return 0;49 }