fork(17) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 100010;
  6.  
  7. typedef unsigned long long LL;
  8.  
  9. int prime[100];
  10. const LL INF = (LL) 1e19;
  11.  
  12. LL memo[65][65][2];
  13. vector <int> a;
  14.  
  15. LL dp (int index, int sum, int tight) {
  16.     LL &res = memo[index][sum][tight];
  17.     if (res == -1) {
  18.         res = 0;
  19.         if (index == a.size()) {
  20.             if (prime[sum])
  21.                 res = 1;
  22.         } else {
  23.             if (tight) {
  24.                 for (int i = 0; i <= a[index]; i++) {
  25.                     if (i == a[index]) {
  26.                         res += dp (index + 1, sum + i, tight);
  27.                     } else {
  28.                         res += dp (index + 1, sum + i, false);
  29.                     }
  30.                 }
  31.             } else {
  32.                 for (int i = 0; i < 2; i++) {
  33.                     res += dp (index + 1, sum + i, false);
  34.                 }
  35.             }
  36.         }
  37.     }
  38.  
  39.     return res;
  40. }
  41.  
  42. LL solve (LL n) {
  43.     if (n == 0)
  44.         return 0;
  45.  
  46.     a.clear();
  47.     while (n) {
  48.         a.push_back (n % 2);
  49.         n /= 2;
  50.     }
  51.     reverse (a.begin(), a.end());
  52.  
  53.     memset (memo, -1, sizeof (memo));
  54.     LL ans = dp (0, 0, 1);
  55.     return ans;
  56. }
  57.  
  58. LL digit_sum (LL n) {
  59.     LL ans = 0;
  60.     while (n) {
  61.         ans += n % 2;
  62.         n /= 2;
  63.     }
  64.     return ans;
  65. }
  66.  
  67. LL brute (LL a, LL b) {
  68.     LL ans = 0;
  69.     for (LL i = a; i <= b; i++) {
  70.         if (prime [digit_sum (i)]) {
  71.             ans ++;
  72.         }
  73.     }
  74.     return ans;
  75. }
  76.  
  77. int isPrime (int n) {
  78.     for (int i = 2; i * i <= n; i++)
  79.         if (n % i == 0)
  80.             return false;
  81.     return true;
  82. }
  83.  
  84. void pre () {
  85.     for (int i = 2; i < 100; i++) {
  86.         prime[i] = isPrime (i);
  87.     }
  88. }
  89.  
  90. int main() {
  91.     pre();
  92.     LL a, b;
  93.     int T;
  94.     cin >> T;
  95.     assert (T >= 1 && T <= 100000);
  96.     while (T--) {
  97.         cin >> a >> b;
  98.         assert (a <= b);
  99.         assert (a >= 1 && a <= INF);
  100.         assert (b >= 1 && b <= INF);
  101.  
  102.         LL ans = solve (b) - solve (a - 1);
  103.         /*
  104.         if (b - a <= 10000) {
  105.             LL ans1 = brute (a, b);
  106.             assert (ans == ans1);
  107.         }
  108.         */
  109.         cout << ans << endl;
  110.     }
  111.     return 0;
  112. }
  113.  
  114.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/numnIE
language:
Text (text 6.10)
created:
10 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!