fork download
copy 
  1. /*
  2.     created by: nitin23329
  3.     on Date: 09/06/21
  4. */
  5.  
  6. import java.io.*;
  7. import java.util.*;
  8. /*****************************************WRITING CODE STARTS HERE******************************************/
  9.  class CodeForces {
  10.     static int[][][][] dp =  new int[11][100][100][2];
  11.     private static int memo(int i,int sum,int currRem,int isBounded,int k,int[] digitArray){
  12.         if(digitArray.length == i) {
  13.             return sum == 0 && currRem  ==0 ? 1 :0;
  14.         }
  15.         if(dp[i][sum][currRem][isBounded]!=-1)return dp[i][sum][currRem][isBounded];
  16.         int ans = 0;
  17.         if(isBounded==1){
  18.             for(int digit = 0 ; digit <= digitArray[i];digit++){
  19.                 int currPlace = (int)((digit * power(10,digitArray.length -i-1))%k);
  20.                 ans += memo(i+1,(sum + digit)%k,(currRem + currPlace)%k,digit == digitArray[i]?1:0,k,digitArray);
  21.             }
  22.         }else {
  23.             for(int digit = 0 ; digit <= 9;digit++) {
  24.                 int currPlace = (int) ((digit * power(10, digitArray.length - i - 1)) % k);
  25.                 ans += memo(i + 1, (sum + digit) % k, (currRem + currPlace) % k, 0, k, digitArray);
  26.             }
  27.         }
  28.         return dp[i][sum][currRem][isBounded] = ans;
  29.     }
  30.     private static int helper(int n,int k){
  31.         int digitLength = countDigitBase10(n);
  32.         int[] digitArray = new int[digitLength];
  33.         int nn = n;
  34.         for(int i = digitLength-1;i>=0;i--){
  35.             digitArray[i] = nn % 10;
  36.             nn/=10;
  37.         }
  38.         // currSum can be digitLength * 9
  39.         // currRem can be upto range 0 to k
  40.  
  41.         for(int i=0;i<digitLength;i++)
  42.             for(int j=0;j<dp[0].length;j++)
  43.                 for(int kk=0;kk<k;kk++)
  44.                     Arrays.fill(dp[i][j][kk],-1);
  45.  
  46.         return memo(0,0,0,1,k,digitArray);
  47.     }
  48.     private static void solve() {
  49.         int a = sc.nextInt();
  50.         int b = sc.nextInt();
  51.         int k = sc.nextInt();
  52.         if(k>=100){
  53.             out.println(0);
  54.             return;
  55.         }
  56.         out.println(helper(b,k) - (a>1?helper(a-1,k):1));
  57.  
  58.     }
  59.  
  60.     /*****************************************WRITING CODE ENDS HERE******************************************/
  61.  
  62.     public static void main(String[] args){
  63.         FIO(false);
  64.         int testCase = 1;
  65.         testCase = sc.nextInt();
  66.         int start = 0;
  67. //        while (testCase-- > 0) solve();
  68.         while (start++<testCase){
  69.             out.print("Case "+start+": ");
  70.             solve();
  71.         }
  72.         closeIO();
  73.     }
  74.  
  75.     static Scanner sc ;                     // FAST INPUT
  76.     static PrintWriter out;                // FAST OUTPUT
  77.     static PrintWriter debug ;             // DEBUG IN FILE : debug.txt
  78.  
  79.  
  80.     /**************************************HELPER FUNCTION STARTS HERE ************************************/
  81.  
  82.     public static int mod = (int) 1e9 + 7;
  83.     public static final int INT_MAX = Integer.MAX_VALUE;
  84.     public static final int INT_MIN = Integer.MIN_VALUE;
  85.     public static final long LONG_MAX = Long.MAX_VALUE;
  86.     public static final long LONG_MIN = Long.MIN_VALUE;
  87.     public static final double DOUBLE_MAX = Double.MAX_VALUE;
  88.     public static final double DOUBLE_MIN = Double.MIN_VALUE;
  89.     public static final String YES = "YES";
  90.     public static final String NO = "NO";
  91.  
  92.     public static void sort(int[] a, boolean isAscending) {
  93.         ArrayList<Integer> temp = new ArrayList<>();
  94.         for (int j : a) temp.add(j);
  95.         sort(temp, isAscending);
  96.         for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  97.     }
  98.  
  99.     public static void sort(long[] a, boolean isAscending) {
  100.         ArrayList<Long> temp = new ArrayList<>();
  101.         for (long ele : a) temp.add(ele);
  102.         sort(temp, isAscending);
  103.         for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
  104.     }
  105.  
  106.     public static void sort(List list, boolean isAscending) {
  107.         if (isAscending)
  108.             Collections.sort(list);
  109.         else Collections.sort(list, Collections.reverseOrder());
  110.     }
  111.     // count the length of a number, time O(1)
  112.     public static int countDigitBase10(long n){
  113.         return (int)(1 + Math.log10(n));
  114.     }
  115.  
  116.     // euclidean algorithm
  117.     public static long gcd(long a, long b) {
  118.         // time O(max (loga ,logb))
  119.         long x = Math.min(a, b);
  120.         long y = Math.max(a, b);
  121.         if (y % x == 0) return x;
  122.         return gcd(y % x, x);
  123.     }
  124.  
  125.     public static long lcm(long a, long b) {
  126.         // lcm(a,b) * gcd(a,b) = a * b
  127.         return (a / gcd(a, b)) * b;
  128.     }
  129.  
  130.     public static long power(long x, long n) {
  131.         // time O(logn)
  132.         long ans = 1;
  133.         while (n > 0) {
  134.             if ((n & 1) == 1) {
  135.                 ans *= x;
  136.                 ans %= mod;
  137.                 n--;
  138.             } else {
  139.                 x *= x;
  140.                 x %= mod;
  141.                 n >>= 1;
  142.             }
  143.         }
  144.         return ans;
  145.     }
  146.  
  147.     public static long factorial(long n) {
  148.         long fact = 1L;
  149.         for (int i = 2; i <= n; i++) fact = (fact * i) % mod;
  150.         return fact;
  151.     }
  152.  
  153.     public static long firstDivisor(long n) {
  154.         if (n == 1 || n == 0) return n;
  155.         for (long i = 2; i * i <= n; i++)
  156.             if (n % i == 0) return i;
  157.         return -1;
  158.     }
  159.  
  160.     public static int ncr(int n, int r) {
  161.         // time O(n+r)
  162.         if (r > n)
  163.             return 0;
  164.         long[] inv = new long[r + 1];
  165.         inv[1] = 1;
  166.         // Getting the modular inversion
  167.         // for all the numbers
  168.         // from 2 to r with respect to m
  169.         for (int i = 2; i <= r; i++) {
  170.             inv[i] = mod - (mod / i) * inv[mod % i] % mod;
  171.         }
  172.         int ans = 1;
  173.         // for 1/(r!) part
  174.         for (int i = 2; i <= r; i++) {
  175.             ans = (int) (((ans % mod) * (inv[i] % mod)) % mod);
  176.         }
  177.         // for (n)*(n-1)*(n-2)*...*(n-r+1) part
  178.         for (int i = n; i >= (n - r + 1); i--) {
  179.             ans = (int) (((ans % mod) * (i % mod)) % mod);
  180.         }
  181.         return ans;
  182.     }
  183.  
  184.     public static long max3(long a, long b, long c) { return max2(max2(a, b), c);}
  185.  
  186.     public static long max2(long a, long b) {return Math.max(a, b);}
  187.  
  188.     public static long min3(long a, long b, long c) {return min2(min2(a, b), c);}
  189.  
  190.     public static long min2(long a, long b) { return Math.min(a, b); }
  191.  
  192.     public static int max3(int a, int b, int c) { return max2(max2(a, b), c); }
  193.  
  194.     public static int max2(int a, int b) { return Math.max(a, b); }
  195.  
  196.     public static int min3(int a, int b, int c) { return min2(min2(a, b), c); }
  197.  
  198.     public static int min2(int a, int b) {
  199.         return Math.min(a, b);
  200.     }
  201.  
  202.     /**************************************HELPER FUNCTION ENDS HERE ************************************/
  203.  
  204.     /*****************************************FAST INPUT STARTS HERE *************************************/
  205.  
  206.     public static void FIO(boolean isDebug){
  207.         sc = new Scanner();
  208.         out = new PrintWriter(new BufferedOutputStream(System.out));
  209.         if(isDebug){
  210.             try {
  211.                 debug = new PrintWriter(new FileOutputStream("debug.txt"));
  212.             }catch (IOException e){
  213.                 e.printStackTrace();
  214.             }
  215.         }
  216.  
  217.     }
  218.     public static void closeIO(){
  219.         sc.close();
  220.         out.flush();
  221.         out.close();
  222.         if(debug!=null){
  223.             debug.flush();
  224.             debug.close();
  225.         }
  226.     }
  227.  
  228.     private static class Scanner {
  229.         private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  230.         private StringTokenizer st = new StringTokenizer("");
  231.  
  232.         public String next() {
  233.             while (!st.hasMoreTokens())
  234.                 try {
  235.                     st = new StringTokenizer(br.readLine());
  236.                 } catch (IOException e) {
  237.                     e.printStackTrace();
  238.                 }
  239.             return st.nextToken();
  240.  
  241.         }
  242.  
  243.         public int nextInt() {
  244.             return Integer.parseInt(next());
  245.         }
  246.  
  247.         public long nextLong() {
  248.             return Long.parseLong(next());
  249.         }
  250.  
  251.         public double nextDouble() {
  252.             return Double.parseDouble(next());
  253.         }
  254.  
  255.         public int[] set_int_array(int n) {
  256.             int[] arr = new int[n];
  257.             for (int i = 0; i < n; i++) arr[i] = nextInt();
  258.             return arr;
  259.         }
  260.  
  261.         public long[] set_long_array(int n) {
  262.             long[] arr = new long[n];
  263.             for (int i = 0; i < n; i++) arr[i] = nextLong();
  264.             return arr;
  265.         }
  266.         public double[] set_double_array(int n){
  267.             double[] arr = new double[n];
  268.             for(int i =0;i<n;i++)arr[i] = sc.nextDouble();
  269.             return arr;
  270.         }
  271.  
  272.         public int[][] set_2D_int_array(int n) {
  273.             return set2DIntArray(n, n);
  274.         }
  275.  
  276.         public int[][] set2DIntArray(int row, int col) {
  277.             int[][] arr = new int[row][col];
  278.             for (int i = 0; i < row; i++)
  279.                 for (int j = 0; j < col; j++)
  280.                     arr[i][j] = nextInt();
  281.             return arr;
  282.         }
  283.  
  284.         public long[][] set_2D_long_array(int n) {
  285.             return set2DlongArray(n, n);
  286.         }
  287.  
  288.         public long[][] set2DlongArray(int row, int col) {
  289.             long[][] arr = new long[row][col];
  290.             for (int i = 0; i < row; i++)
  291.                 for (int j = 0; j < col; j++)
  292.                     arr[i][j] = nextLong();
  293.             return arr;
  294.         }
  295.  
  296.         public char[][] set_2D_char_array(int n) {
  297.             return set2DCharArray(n, n);
  298.         }
  299.  
  300.         public char[][] set2DCharArray(int row, int col) {
  301.             char[][] ch = new char[row][col];
  302.             for (int i = 0; i < row; i++)
  303.                 ch[i] = sc.next().toCharArray();
  304.             return ch;
  305.         }
  306.  
  307.         public void close() {
  308.             try {
  309.                 br.close();
  310.             } catch (IOException e) {
  311.                 e.printStackTrace();
  312.             }
  313.         }
  314.     }
  315.     /*****************************************FAST INPUT ENDS HERE *************************************/
  316. }
  317.  
Success #stdin #stdout 0.11s 52496KB
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/Te0I8k
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!