fork(1) 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. #define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
  23. #define pw(x) (1ll<<(x))
  24.  
  25. typedef long long ll;
  26.  
  27. ll g[32];
  28. ll pr_ans[63];
  29. VI divs[63];
  30.  
  31. inline void upd(int i)
  32. {
  33.     fori(j,divs[i])
  34.         g[i]-=g[*j];
  35. }
  36.  
  37. void prec()
  38. {
  39.     for(int i = 1;i < 61;i++)
  40.     {
  41.         for(int j=1;j * j <= i && j < i;j++)
  42.             if (i%j==0)
  43.             {
  44.                 divs[i].pb(j);
  45.                 int d = i / j;
  46.                 if (d != j && d < i)
  47.                     divs[i].pb(d);
  48.             }
  49.         sort(divs[i].begin(),divs[i].end());
  50.     }
  51.     clr(g);
  52.     for(int i=1;i<31;i++)
  53.     {
  54.         g[i] = pw(i-1);
  55.         upd(i);
  56.     }
  57.  
  58.     clr(pr_ans);
  59.     for(int i=1;i<61;i++)
  60.     {
  61.         pr_ans[i] = pr_ans[i-1];
  62.         fori(j,divs[i])
  63.             pr_ans[i] += g[*j];
  64.     }
  65. }
  66. inline int lg(ll n)
  67. {
  68.     int l = 0;
  69.     while (n)
  70.     {
  71.         l++;
  72.         n>>=1;
  73.     }
  74.     return l;
  75. }
  76.  
  77. ll f(ll n)
  78. {
  79.     if (n <= 1) return 0;
  80.     ll ans = 0;
  81.     int l = lg(n);
  82.     ans += pr_ans[l-1];
  83.     clr(g);
  84.     fori(it, divs[l])
  85.     {
  86.         int i = *it;
  87.         ll t = n >> (l-i);
  88.         ll p = t;
  89.         forn(j,l/i-1)
  90.             p = (p << i) + t;
  91.         if (p <= n) g[i]++;
  92.         g[i] += t - pw(i-1);
  93.         upd(i);
  94.         ans += g[i];
  95.     }
  96.     return ans;
  97. }
  98.  
  99. int main()
  100. {
  101.     prec();
  102.     ll l,r;
  103.     cin >> l >> r;
  104.     cout << f(r) - f(l-1);
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0.01s 2864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-538596157
https://ideone.com/MOfBE
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!