[Codechef] COPRIME3 - Coprime Triples

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : COPRIME3 - Coprime Triples
Source            : Codechef
Category          : Number Theory
Algorithm         : Mobius Inversion Formula
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long        ll;
 
static const int MAXN = 1e6 + 5;
 
ll arr[MAXN], fre[MAXN], divi[MAXN];
bool is_composite[MAXN];
vector <int> prime;
 
void seive(int n)
{
    fill(is_composite, is_composite+n, false);
    is_composite[1] = true;
    for (int i = 2; i < n; i++)
    {
        if (!is_composite[i]) prime.push_back(i);
        divi[i] = fre[i];
        for (int j = 2; i*j < n; j++)
        {
            is_composite[ i*j ] = true;
            divi[i] += fre[i * j];
        }
    }
}
 
ll mobius[MAXN];
 
void mobiusCalc(ll n)
{
    for (int i = 1; i <= n; i++) mobius[i] = 1;
    int sqrtn = sqrt(n);
    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;
    }
}
 
ll Count(int n, int maxn)
{
    ll triplets = 0;
    for (int d = 1; d <= maxn; d++)
    {
        ll nC3 = divi[d] * (divi[d] - 1) * (divi[d] - 2) / 6;
        triplets += mobius[d] * nC3;
    }
    return triplets;
}
 
int main()
{
    //freopen("input_coprime3.txt", "r", stdin);
 
    int n;
    scanf("%d", &n);
    ll maxn = -1;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", arr+i);
        maxn = max(maxn, arr[i]);
        fre[ arr[i] ]++;
    }
    divi[1] = n;
    seive(MAXN);
    mobiusCalc(maxn);
    printf("%lld\n", Count(n, maxn));
}