fork download
copy 
  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.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  147.         StringTokenizer st = new StringTokenizer("");
  148.  
  149.         String next(){
  150.             while(!st.hasMoreTokens()){
  151.                 try{
  152.                     st = new StringTokenizer(br.readLine());
  153.                 }catch(IOException e){
  154.                     e.printStackTrace();
  155.                 }
  156.             }
  157.  
  158.             return st.nextToken();
  159.         }
  160.  
  161.         String ns(){
  162.             String s = new String();
  163.             try{
  164.                 s = br.readLine().trim();
  165.             }catch(IOException e){
  166.                 e.printStackTrace();
  167.             }
  168.  
  169.             return s;
  170.         }
  171.  
  172.         int[] arr(int n){
  173.             int[] a = new int[n];
  174.             for(int i = 0; i < n; i++) a[i] = ni();
  175.             return a;
  176.         }
  177.  
  178.         char[] nc(){return ns().toCharArray();}
  179.         int ni(){return Integer.parseInt(next());}
  180.         long nl(){return Long.parseLong(next());}
  181.         double nd(){return Double.parseDouble(next());}
  182.     }
  183. }
Success #stdin #stdout 0.12s 36472KB
comments (?)
stdin
copy 
3
1 20 1
1 20 2
1 1000 4
stdout
copy 
Case 1: 20
Case 2: 5
Case 3: 64
https://ideone.com/UB1h7V
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!