fork download 
  1. /* Authors: Vu Hoang Bach from Phuoc Hoa Secondary School */
  2. /* Enjoy TheFatRat's music while reading my code. Link: https://w...content-available-to-author-only...e.com/watch?v=GCx9FU59FJc&t=669s */
  3.  
  4. //#pragma GCC optimize("O3", "unroll-loops")
  5. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  6.  
  7. #include <bits/stdc++.h>
  8. #define ldb long double
  9. //#define double ldb
  10. #define db double
  11. #define unomap unordered_map
  12. #define unoset unordered_set
  13. #define endl '\n'
  14. #define str string
  15. #define strstr stringstream
  16. #define sz(a) a.size()
  17. #define ll long long
  18. //#define int ll
  19. #define pii pair <int, int>
  20. #define pll pair <ll, ll>
  21. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  22. #define ull unsigned ll
  23. #define fir first
  24. #define sec second
  25. #define idc cin.ignore()
  26. #define lb lower_bound
  27. #define ub upper_bound
  28. #define all(s) s.begin(), s.end()
  29. #define rev reverse
  30. #define sigma ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  31. #define skibidi int main
  32. #define rizz signed main
  33. #define gcd __gcd
  34. #define found(a, mp) mp.find(a) != mp.end()
  35. #define game_over exit(0);
  36. #define stfu return 0;
  37. #define stop break;
  38. #define pushb push_back
  39. #define popb pop_back
  40. #define pushf push_front
  41. #define popf pop_front
  42. #define mul2x(a, x) a << x
  43. #define div2x(a, x) a >> x
  44. #define no_check continue;
  45. #define lcm(a, b) a / __gcd(a, b) * b
  46. #define log_base(x, base) log(x) / log(base)
  47. #define debug clog << "No errors!"; game_over;
  48. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  49. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  50. #define fors(i, a, b) for (int i = a; i >= b; --i)
  51. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  52. #define meme memset
  53. #define pqueue priority_queue
  54. #define sqrt sqrtl
  55. #define name "test"
  56. #define want_digit(x) cout << fixed << setprecision(x);
  57. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  58. using namespace std;
  59. const int MOD = 1e9 + 7; // 998244353
  60. const int inf = 1e9;
  61. const ll INF = 1e18;
  62. const int N = 9;
  63. const int K = 45;
  64.  
  65. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  66. ll random(const ll &L, const ll &R)
  67. {
  68.     return uniform_int_distribution<ll> (L, R) (rng);
  69. }
  70.  
  71. vector<int> v;
  72.  
  73. bool is_prime[K + 5];
  74. void sieve(const int &lim)
  75. {
  76.     is_prime[0] = is_prime[1] = true;
  77.     for (int i = 2; i * i <= lim; ++i)
  78.         if (!is_prime[i])
  79.             for (int j = i * i; j <= lim; j += i) is_prime[j] = true;
  80. }
  81.  
  82. bool check_prime(int x)
  83. {
  84.     if (x < 2) return false;
  85.     return !is_prime[x];
  86. }
  87.  
  88. int dp[N + 5][K + 5][K + 5][2];
  89. int f(int pos, int even, int odd, bool ok)
  90. {
  91.     if (pos == sz(v))
  92.         return check_prime(even - odd);
  93.  
  94.     int &tmp = dp[pos][even][odd][ok];
  95.     if (tmp != -1) return tmp;
  96.     tmp = 0;
  97.     int fin = (ok ? 9 : v[pos]);
  98.     forw(i, 0, fin)
  99.         tmp += f(pos + 1, even + i * (!(pos & 1)), odd + i * (pos & 1), (ok | i < fin));
  100.     return tmp;
  101. }
  102.  
  103. int calc(int n)
  104. {
  105.     v.clear();
  106.     forw(i,1,10) v.pushb(n % 10), n /= 10;
  107.     reverse(all(v));
  108.  
  109.     meme(dp, -1, sizeof(dp));
  110.     return f(0, 0, 0, 0);
  111. }
  112.  
  113. int a, b;
  114. void cook()
  115. {
  116.     cin >> a >> b;
  117.     if (a > b) swap(a, b);
  118.     cout << calc(b) - calc(a - 1) << endl;
  119. }
  120.  
  121. skibidi()
  122. //rizz()
  123. {
  124.     srand(time(NULL));
  125.     sigma;
  126.     /*
  127.     if (fopen(name".INP", "r"))
  128.     {
  129.         freopen(name".INP", "r", stdin);
  130.         freopen(name".OUT", "w", stdout);
  131.     }
  132.     */
  133.     sieve(K);
  134.     int numTest = 1;
  135. //    cin >> numTest;
  136.     while (numTest--)
  137.     {
  138.         cook();
  139.     }
  140.     stfu;
  141. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
50 100
stdout 
18
https://ideone.com/eDfOrt
language:
C++14 (gcc 8.3)
created:
13 days 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!