fork(7) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-538590904
https://ideone.com/96ZjG
language:
C++ (gcc 8.3)
created:
11 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!