fork(7) download
  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <ctime>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <map>
  10. #include <queue>
  11. #include <set>
  12. #include <sstream>
  13. #include <string>
  14. #include <vector>
  15.  
  16. using namespace std;
  17.  
  18. #define pb push_back
  19. #define VI vector <int>
  20. #define clr(x) memset((x),0,sizeof(x))
  21. #define forn(i, n) for(int i=0; i<(int)(n); i++)
  22.  
  23. #define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
  24.  
  25. #define pw(x) (1ll<<(x))
  26.  
  27. typedef long long ll;
  28.  
  29. ll g[32];
  30. VI divs[63];
  31. void prec()
  32. {
  33. for(int i=1;i<61;i++)
  34. for(int j=1;j<i;j++)
  35. if (i%j==0)
  36. divs[i].pb(j);
  37. }
  38. inline int lg(ll n)
  39. {
  40. int l = 0;
  41. while (n)
  42. {
  43. l++;
  44. n>>=1;
  45. }
  46. return l;
  47. }
  48.  
  49. inline void upd(int i)
  50. {
  51. fori(j,divs[i])
  52. g[i]-=g[*j];
  53. }
  54.  
  55. ll f(ll n)
  56. {
  57. if (n<=1) return 0;
  58. ll ans = 0;
  59. int l = lg(n);
  60. ans+=f(pw(l-1) - 1);
  61. clr(g);
  62. fori(it, divs[l])
  63. {
  64. int i = *it;
  65. ll t = n >> (l-i);
  66. ll p = t;
  67. forn(j,l/i-1)
  68. p = (p << i) + t;
  69. if (p <= n) g[i]++;
  70. g[i] += t - pw(i-1);
  71. upd(i);
  72. ans += g[i];
  73. }
  74. return ans;
  75. }
  76.  
  77. int main()
  78. {
  79. prec();
  80. ll l,r;
  81. cin >> l >> r;
  82. cout << f(r)-f(l-1);
  83. return 0;
  84. }
  85.  
Success #stdin #stdout 0.02s 2816KB
stdin
Standard input is empty
stdout
-538590904