fork download 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <string>
  6. #include <cstdio>
  7. using namespace std;
  8. char s[22];
  9. long long int n;
  10. long long int p[11];
  11. long long dp[22][2][2];
  12. long long poww[22];
  13. void pre()
  14. {
  15.      poww[0] = 1;
  16.      for ( int i = 1; i <= 18; i++ ) poww[i] = poww[i-1]*10;
  17.      return;
  18. }
  19. long long f(int idx, int tight, int flag)
  20. {
  21. 	if ( idx == n ) {
  22. 		if ( flag ) return 1;
  23. 		return 0;
  24. 	}
  25. 	long long &ans = dp[idx][tight][flag];
  26. 	if ( ans != -1 ) return ans;
  27. 	ans = 0;
  28. 	if ( tight == 0 ) {
  29.         if ( flag ) {
  30.             ans = poww[n-idx];
  31. 		    return ans;
  32. 	    } 
  33. 		for ( int i = 0; i <= 9; i++ ) {
  34. 			ans += f(idx+1, 0, flag | p[i]);
  35. 		}
  36. 	}
  37. 	else {
  38. 		for ( int i = 0; i <= s[idx]-49; i++ ) {
  39. 			ans += f(idx+1, 0, flag | p[i]);
  40. 		}
  41. 		ans += f(idx+1, 1, flag | p[s[idx]-48]);
  42. 	}
  43. 	return ans;
  44. }
  45. int main()
  46. {
  47. 	p[2] = p[3] = p[5] = p[7] = 1;
  48. 	int t;
  49. 	pre();
  50. 	scanf("%d", &t);
  51. 	while ( t-- ) {
  52.         scanf("%s", s);  
  53.         long long int i,j,k;
  54. 		n = (long long int)(strlen(s));
  55. 		for (i = 0; i < n; i++ ) {
  56.             for ( j = 0; j < 2; j++ ) {
  57.                 for (  k = 0; k < 2; k++ ) dp[i][j][k] = -1;
  58.             }
  59.         }
  60. 		long long ans = f(0,1,0);
  61. 		printf("%lld\n", ans);
  62. 	}
  63. 	return 0;
  64. }
Success #stdin #stdout 0s 3472KB
comments ()
stdin 
2
100
120
stdout 
64
73
https://ideone.com/iRncQo
language:
C++14 (gcc 8.3)
created:
8 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!