fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define LL long long int
  5. #define LD long double
  6. #define inp_s ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
  7. #define MOD 1000000007
  8. #define INF 1000000000
  9. #define pii pair<int, int>
  10.  
  11. // natural, no 9, and not divisible by 9
  12.  
  13. vector<int> v;
  14.  
  15. LL DP[20][3][10];
  16.  
  17. void reset(){
  18.       for(int i=0 ; i<20 ; i++){
  19.             for(int j=0 ; j<3 ; j++){
  20.                   for(int k=0 ; k<10 ; k++){
  21.                         DP[i][j][k] = -1;
  22.                   }
  23.             }
  24.       }
  25. }
  26.  
  27. LL compute(int pos, int f, int mod){
  28.       if(pos == v.size()){
  29.             if(mod != 0) return 1LL;
  30.             return 0LL;
  31.       }     
  32.       if(DP[pos][f][mod] != -1) return DP[pos][f][mod];
  33.  
  34.       LL ans = 0;
  35.  
  36.       int rng = (f == 1) ? 8 : v[pos];
  37.  
  38.       for(int d=0 ; d<=rng ; d++){
  39.             int n_f = (f | (d < v[pos]));
  40.             int n_mod = (mod * 10 + d) % 9;
  41.             ans += compute(pos+1, n_f, n_mod);
  42.       }
  43.       return (DP[pos][f][mod] = ans);
  44. }
  45.  
  46.  
  47. LL solve(LL x){
  48.       if(x <= 0) return 0;
  49.       v.clear();
  50.       while(x > 0){
  51.             int rem = x % 10;
  52.             v.push_back(rem);
  53.             x = x / 10;
  54.       }
  55.       reverse(v.begin(), v.end());
  56.       reset();
  57.       LL ans = compute(0, 0, 0);
  58.       return ans;
  59. }
  60.  
  61. int main(){
  62.       int T;
  63.       cin >> T;
  64.       for(int t=1 ; t<=T ; t++){
  65.             LL l, r;
  66.             cin >> l >> r;
  67.             LL ans = solve(r) - solve(l-1);
  68.             cout << "Case #" << t << ": " << ans << '\n';
  69.       }
  70.       return 0;
  71. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
16 26
88 102
1 100
1 1000000000000000000
stdout
copy 
Case #1: 9
Case #2: 4
Case #3: 73
Case #4: 133417453597332553
https://ideone.com/qMFsuh
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!