fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5.  
  6. #define int long long
  7. using namespace std;
  8. vector<int> num;
  9. int a, b, k;
  10. int dp[12][90][90][2];
  11.  
  12. int go(int pos, int val, int sum, int f) {
  13.     if (pos == num.size()) {
  14.         if (sum == 0 and val == 0)
  15.             return 1;
  16.         return 0;
  17.     }
  18.  
  19.     int &res = dp[pos][val][sum][f];
  20.     if (res != -1)
  21.         return res;
  22.     res = 0;
  23.     int LMT;
  24.     if (f == 0)
  25.         LMT = num[pos];
  26.     else
  27.         LMT = 9;
  28.  
  29.     for (int dgt = 0; dgt <= LMT; dgt++) {
  30.         int nf = f;
  31.         if (f == 0 and dgt < LMT)nf = 1;
  32.         res += go(pos + 1, (val * 10 + dgt) % k, (sum + dgt) % k, nf);
  33.     }
  34.     return res;
  35. }
  36.  
  37.  
  38. int solve(int a) {
  39.     num.clear();
  40.     while (a > 0)
  41.         num.push_back(a % 10), a /= 10;
  42.     reverse(num.begin(), num.end());
  43.  
  44.     memset(dp, -1, sizeof dp);
  45.     return go(0, 0, 0, 0);
  46. }
  47.  
  48. int32_t main() {
  49.  
  50.     int t;
  51.     cin >> t;
  52.     for (int i = 1; i <= t; i++) {
  53.         cin >> a >> b >> k;
  54.         int ans;
  55.         if (k > 83)
  56.             ans = 0;
  57.         else ans = solve(b) - solve(a - 1);
  58.         cout << "Case " << i << ": " << ans << endl;
  59.     }
  60.     return 0;
  61. }
Success #stdin #stdout 0s 16752KB
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/EeSbEU
language:
C++14 (gcc 8.3)
created:
5 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!