fork download 
  1. #include <stdio.h>
  2. #include <climits>
  3. #include <iostream>
  4. #include <map>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <set>
  8. #include <stack>
  9. #include <deque>
  10. #include <vector>
  11. #include <stdlib.h>
  12. #include <string>
  13. #include <string.h>
  14. #include <utility>
  15. #include <queue>
  16.  
  17. using namespace std;
  18.  
  19. #define ll long long
  20. #define sl(n) scanf("%lld", &n)
  21. #define sf(n) scanf("%lf", &n)
  22. #define si(n) scanf("%d", &n)
  23. #define ss(n) scanf("%s", n)
  24. #define pii pair <int, int>
  25. #define pll pair <long long, long long>
  26. #define pb push_back
  27.  
  28. deque <ll> digits;
  29.  
  30. ll k;
  31.  
  32. ll pwr(ll b, ll p)
  33. {
  34.     if (p == 0)
  35.         return 1;
  36.  
  37.     ll x = pwr(b, p/2);
  38.  
  39.     x = (x*x)%k;
  40.  
  41.     if (p%2 == 0)
  42.         return x;
  43.     else return (b*x)%k;
  44. }
  45.  
  46. ll dp[10][2][82][82];
  47.  
  48. ll solve(ll i, ll isSmall, ll mod, ll mod2)
  49. {
  50.     if (i == -1)
  51.     {
  52.         if (mod == 0 && mod2 == 0)
  53.             return 1;
  54.         else return 0;
  55.     }
  56.  
  57.     if (dp[i][isSmall][mod][mod2] != -1)
  58.         return dp[i][isSmall][mod][mod2];
  59.  
  60.     ll limit = isSmall == 1? 9 : digits[i], ans = 0;
  61.  
  62.     //  cout << i << " " << isSmall << " " << mod << " " << limit << " " << digits[i] << endl;
  63.  
  64.     for (ll j = 0; j <= limit; j++)
  65.     {
  66.         ans += solve(i - 1, isSmall | (j < digits[i]), (mod + (j*pwr(10, i))%k)%k, (mod2 + j)%k);
  67.     }
  68.  
  69.     return (dp[i][isSmall][mod][mod2] = ans);
  70. }
  71.  
  72. int main ()
  73. {
  74.     //  freopen("inl.txt", "r", stdin);
  75.     // freopen("outu.txt", "w", stdout);
  76.     //  ios_base::sync_with_stdio(0); // no printf/scanf must be present
  77.     ll cs, t, i, j, n, x, y, z, ans, q, m;
  78.  
  79.     sl(t);
  80.  
  81.     for (cs = 1; cs <= t; cs++)
  82.     {
  83.         sl(x);
  84.         sl(y);
  85.         sl(k);
  86.  
  87.         if (k <= 81)
  88.         {
  89.             digits.clear();
  90.  
  91.             while (y != 0)
  92.             {
  93.                 digits.push_back(y%10);
  94.                 y /= 10;
  95.             }
  96.  
  97.             memset(dp, -1, sizeof(dp));
  98.  
  99.             ans = solve(digits.size() - 1, 0, 0, 0);
  100.  
  101.             cout << ans << endl;
  102.  
  103.             x--;
  104.  
  105.             if (x != 0)
  106.             {
  107.                 digits.clear();
  108.  
  109.                 while (x != 0)
  110.                 {
  111.                     digits.push_back(x%10);
  112.                     x /= 10;
  113.                 }
  114.  
  115.                 memset(dp, -1, sizeof(dp));
  116.  
  117.                 ans -= solve(digits.size() - 1, 0, 0, 0);
  118.             }
  119.             else ans--;
  120.         }
  121.         else ans = 0;
  122.         printf("Case %lld: %lld\n", cs, ans);
  123.     }
  124.  
  125.     return 0;
  126. }
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin 
3
1 20 1
1 20 2
1 1000 4
stdout 
21
Case 1: 20
6
Case 2: 5
65
Case 3: 64
https://ideone.com/uohyyS
language:
C++14 (gcc 8.3)
created:
2 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!