fork(15) 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
stdin
Standard input is empty
stdout

Standard output is empty