fork download
copy 
  1. #include <cstring>
  2. #include <iostream>
  3. #include <sstream>
  4. using namespace std;
  5.  
  6. long long memo[10][10][10][8][27][20];
  7.  
  8. long long step_found(int a, int b, int c, int found, int next_digit) {
  9.     // computes the next "found" bitmask if I'm looking for the digits "a", "b", "c"
  10.     // and see the next digit "next_digit"
  11.     if (next_digit == a && !(found&4)) return found|4;
  12.     if (next_digit == b && !(found&2)) return found|2;
  13.     if (next_digit == c && !(found&1)) return found|1;
  14.     if (next_digit > c) return -1;
  15.     return found;
  16. }
  17.  
  18. long long go(int a, int b, int c, int found, int rem, int left) {
  19.     // a,b,c = the three largest digits we want to have (a >= b >= c)
  20.     // found = bitmask saying which of them we already have
  21.     // rem = the remainder so far
  22.     // left = the number of digits still left to fill in
  23.  
  24.     if (left == 0) return (found==7 && rem==0); // we are at the end -- did we construct a valid number?
  25.  
  26.     long long &result = memo[a][b][c][found][rem][left];
  27.     if (result != -1) return result;
  28.     result = 0;
  29.     for (int d=0; d<=9; ++d) {
  30.         // try appending the next digit
  31.         int next_rem = (10*rem + d) % (a+b+c);
  32.         int next_found = step_found(a, b, c, found, d);
  33.         if (next_found != -1) result += go(a, b, c, next_found, next_rem, left-1);
  34.     }
  35.     return result;
  36. }
  37.  
  38. long long solve(long long UB) {
  39.     // count the good numbers in [1,UB)
  40.  
  41.     // convert UB to string to count its digits and get its prefixes easily
  42.     stringstream ss; ss << UB;
  43.     string S = ss.str();
  44.     int D = S.size();
  45.  
  46.     long long answer = 0;
  47.     // try all possibilities for the three largest digits
  48.     for (int a=1; a<=9; ++a) for (int b=0; b<=a; ++b) for (int c=0; c<=b; ++c) {
  49.  
  50.         // first, count all numbers shorter than UB: iterate over their length and first digit
  51.         for (int len=3; len<D; ++len) {
  52.             for (int first=1; first<=9; ++first) {
  53.                 int found = step_found(a, b, c, 0, first);
  54.                 if (found != -1) answer += go(a, b, c, found, first%(a+b+c), len-1);
  55.             }
  56.         }
  57.  
  58.         // next, for each prefix of UB count all numbers with a smaller last digit
  59.         int prefix_rem = 0, prefix_found = 0;
  60.         for (int p=1; p<=D; ++p) {
  61.             int pd = S[p-1]-'0';
  62.             for (int d=0; d<pd; ++d) {
  63.                 if (p==1 && d==0) continue; // we don't want to count numbers with a leading zero
  64.                 int next_found = step_found(a, b, c, prefix_found, d);
  65.                 if (next_found != -1) answer += go(a, b, c, next_found, (10*prefix_rem+d)%(a+b+c), D-p);
  66.             }
  67.             prefix_rem = (10*prefix_rem + pd) % (a+b+c);
  68.             prefix_found = step_found(a, b, c, prefix_found, pd);
  69.             if (prefix_found == -1) break;
  70.         }
  71.     }
  72.     return answer;
  73. }
  74.  
  75. int main() {
  76.     memset(memo,-1,sizeof(memo));
  77.     int T; cin >> T;
  78.     while (T--) { long long A, B; cin >> A >> B; cout << (solve(B+1) - solve(A)) << endl; }
  79. }
Success #stdin #stdout 0.13s 37192KB
comments (?)
stdin
copy 
4
147 246
147 247
12345 12350
100 999999999999999999
stdout
copy 
27
28
1
40836573910577667
https://ideone.com/9pHuFs
language:
C++14 (gcc 8.3)
created:
8 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!