fork download
  1. import static java.lang.Math.max;
  2. import static java.lang.Math.min;
  3. import static java.lang.Math.abs;
  4. import java.io.*;
  5. import java.util.*;
  6.  
  7. public class Main
  8. {
  9. static int a, b, k;
  10. static int[] arr;
  11. static char[] s;
  12. static Integer[][][][] dp;
  13. static int[] num;
  14. public static void main(String[] args) throws IOException
  15. {
  16. f = new Flash();
  17. out = new PrintWriter(System.out);
  18.  
  19. int T = ni();
  20. for(int tc = 1; tc <= T; tc++){
  21. a = ni(); b = ni(); k = ni();
  22. sop("Case " + tc + ": " + fn());
  23. }
  24.  
  25. out.flush(); out.close();
  26. }
  27.  
  28. static int fn()
  29. {
  30. return solve(b) - solve(a-1);
  31. }
  32.  
  33. static int solve(int n){
  34. int LEN = len(n);
  35. num = new int[LEN];
  36. int x = LEN-1;
  37. while(n > 0){
  38. int d = n%10;
  39. num[x--] = d;
  40. n /= 10;
  41. }
  42.  
  43. dp = new Integer[LEN][k][2][k];
  44. return recurse(0, 0, 0, 0, LEN-1);
  45. }
  46.  
  47. // 6452
  48. // (6*10^3) + (4*10^2) + (5*10^1) + (2*10^0);
  49. // 6000 + 400 + 50 + 2 = 6452
  50. // (x1 + x2) % p == (x1%p + x2%p) % p
  51. static int recurse(int pos, int rem, int f, int rem2, int p){
  52. if(pos == num.length){
  53. if(rem == 0 && rem2 == 0) return 1;
  54. return 0;
  55. }
  56.  
  57. if(dp[pos][rem][f][rem2] != null) return dp[pos][rem][f][rem2];
  58. int max;
  59. if(f == 0) max = num[pos];
  60. else max = 9;
  61.  
  62. int tens = 1;
  63. for(int i = 1; i <= p; i++){
  64. tens *= 10;
  65. tens %= k;
  66. }
  67.  
  68. int ans = 0;
  69. for(int d = 0; d <= max; d++){
  70. int nrem = rem;
  71. nrem += d; nrem %= k;
  72.  
  73. int nrem2 = rem2;
  74. nrem2 += d*tens; nrem2 %= k;
  75.  
  76. int nf = f;
  77. if(f == 0 && d < num[pos]) nf = 1;
  78.  
  79. ans += recurse(pos+1, nrem, nf, nrem2, p-1);
  80. }
  81.  
  82. return dp[pos][rem][f][rem2] = ans;
  83. }
  84.  
  85. static int len(int n){
  86. int ret = 0;
  87. while(n > 0){
  88. n /= 10;
  89. ret++;
  90. }
  91.  
  92. return ret;
  93. }
  94.  
  95. static Flash f;
  96. static PrintWriter out;
  97. static final long mod = (long)1e9+7;
  98. static final long inf = Long.MAX_VALUE;
  99. static final int _inf = Integer.MAX_VALUE;
  100. static final int maxN = (int)5e5+5;
  101. static long[] fact, inv;
  102.  
  103. static void sort(int[] a){
  104. List<Integer> A = new ArrayList<>();
  105. for(int i : a) A.add(i);
  106. Collections.sort(A);
  107. for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
  108. }
  109.  
  110. static void sort(long[] a){
  111. List<Long> A = new ArrayList<>();
  112. for(long i : a) A.add(i);
  113. Collections.sort(A);
  114. for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
  115. }
  116.  
  117. static void print(int[] a){
  118. StringBuilder sb = new StringBuilder();
  119. for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
  120. sop(sb);
  121. }
  122.  
  123. static void print(long[] a){
  124. StringBuilder sb = new StringBuilder();
  125. for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
  126. sop(sb);
  127. }
  128.  
  129. static int swap(int itself, int dummy){return itself;}
  130. static long swap(long itself, long dummy){return itself;}
  131. static void sop(Object o){out.println(o);}
  132. static int ni(){return f.ni();}
  133. static long nl(){return f.nl();}
  134. static double nd(){return f.nd();}
  135. static String next(){return f.next();}
  136. static String ns(){return f.ns();}
  137. static char[] nc(){return f.nc();}
  138. static int[] arr(int len){return f.arr(len);}
  139. static int gcd(int a, int b){if(b == 0) return a; return gcd(b, a%b);}
  140. static long gcd(long a, long b){if(b == 0) return a; return gcd(b, a%b);}
  141. static int lcm(int a, int b){return (a*b)/gcd(a, b);}
  142. static long lcm(long a, long b){return (a*b)/gcd(a, b);}
  143.  
  144. static class Flash
  145. {
  146.  
  147. String next(){
  148. while(!st.hasMoreTokens()){
  149. try{
  150. st = new StringTokenizer(br.readLine());
  151. }catch(IOException e){
  152. e.printStackTrace();
  153. }
  154. }
  155.  
  156. return st.nextToken();
  157. }
  158.  
  159. String ns(){
  160. String s = new String();
  161. try{
  162. s = br.readLine().trim();
  163. }catch(IOException e){
  164. e.printStackTrace();
  165. }
  166.  
  167. return s;
  168. }
  169.  
  170. int[] arr(int n){
  171. int[] a = new int[n];
  172. for(int i = 0; i < n; i++) a[i] = ni();
  173. return a;
  174. }
  175.  
  176. char[] nc(){return ns().toCharArray();}
  177. int ni(){return Integer.parseInt(next());}
  178. long nl(){return Long.parseLong(next());}
  179. double nd(){return Double.parseDouble(next());}
  180. }
  181. }
Success #stdin #stdout 0.12s 36472KB
stdin
3
1 20 1
1 20 2
1 1000 4
stdout
Case 1: 20
Case 2: 5
Case 3: 64