[POJ] Sky Code

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Sky Code
Source            : POJ
Category          : Number Theory
Algorithm         : Mobius Inversion Formula
Verdict           : Accepted 

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
 
using namespace std;
 
typedef long long        ll;
 
static const int MAXN = 10000 + 5;
 
ll arr[MAXN], fre[MAXN], divi[MAXN];
bool is_composite[MAXN];
vector <int> prime;
 
void seive(int n)
{
    for (int i = 1; i <= n; i++) is_composite[i] = false;
    is_composite[1] = true;
    prime.clear();
    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(double(n));
    int sz = prime.size();
    for (int i = 0; i < sz; i++)
    {
        int p = prime[i];
        if (p > sqrtn)
            break;
        int x = p*p;
        for (int j = x; j <= n; j += x)
            mobius[j] = 0;
    }
    for (int i = 0; i < sz; i++)
    {
        int p = prime[i];
        for (int j = p; j <= n; j += p)
            mobius[j] *= -1;
    }
}
 
ll Count(int n, int maxn)
{
    ll ans = 0;
    for (int d = 1; d <= maxn; d++)
    {
        ll nC4 = divi[d] * (divi[d] - 1) * (divi[d] - 2) * (divi[d] - 3) / 24;
        ans += mobius[d] * nC4;
    }
    return ans;
}
 
 
int main()
{
    //freopen("input_skyCode.txt", "r", stdin);
 
    seive(10000);
    mobiusCalc(10000);

    int n;
    while (scanf("%d", &n) == 1)
    {
        ll maxn = -1;
        for (int i = 0; i < n; i++)
        {
            scanf("%lld\n", arr+i);
            maxn = max(maxn, arr[i]);
            fre[ arr[i] ]++;
        }
        divi[1] = n;
        seive(maxn);
        printf("%lld\n", Count(n, maxn));
        memset(fre, 0, sizeof fre);
        memset(divi, 0, sizeof divi);
    }
}