[Gym] Coprime Integers

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Coprime Integers
Source            : Codeforces Gym
Category          : Number Theory
Algorithm         : Mobius Inversion Formula, Bitwise Sieve
Verdict           : Accepted 

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll                long long
 
inline int setbit(int mask, int pos)        { return mask |= (1 << pos); }
inline int resetbit(int mask, int pos)      { return mask &= ~(1 << pos); }
inline int togglebit(int mask, int pos)     { return mask ^= (1 << pos); }
inline bool checkbit(int mask, int pos)     { return (bool)(mask & (1 << pos)); }
 
static const int maxn = 1e7 + 7;
static const int mx = 1e8;
 
int status[(mx/32)+2];
vector <int> prime;
 
inline void sieve(int N)
{
      int sqrtN = int(sqrt(N));
      for(int i = 3; i <= sqrtN; i += 2)
      {
            if(Check(status[i>>5], i&31) == 0)
            {
                  for(int j = i*i; j <= N; j += (i<<1) )
                  {
                        status[j>>5] = Set(status[j>>5], j & 31);
                  }
            }
      }
      prime.emplace_back(2);
      for(int i = 3; i <= N; i += 2)
      {
            if(Check(status[i>>5], i & 31) == 0)
            {
                  prime.emplace_back(i);
            }
      }
}
 
ll mobius[maxn];
 
inline void mobiusCalc(int n)
{
      for (int i = 1; i <= n; i++) mobius[i] = 1;
      int sqrtn = sqrt(n*1.0);
      for (int p : prime)
      {
            if (p > sqrtn) break;
            int x = p*p;
            for (int j = x; j <= n; j += x) mobius[j] = 0;
      }
      for (int p : prime)
      {
            for (int j = p; j <= n; j += p) mobius[j] *= -1;
      }
}
 
inline ll get(ll n, ll d)
{
      return n / d;
}
 
inline ll Count(ll a, ll b, ll c, ll d)
{
      ll ming = min(b, d);
      ll ans = 0;
      for (int dd = 1; dd <= ming; dd++)
      {
            ll add = (get(b, dd) - get(a-1, dd)) * (get(d, dd) - get(c-1, dd));
            ans += mobius[dd] * add;
      }
      return ans;
}
 
int main()
{
      sieve(maxn - 3);
      mobiusCalc(maxn-3);
      ll a, b, c, d;
      cin >> a >> b >> c >> d;
      cout << Count(a, b, c, d) << endl;
}