Cod sursa(job #2460092)

Utilizator ciutanpCiuta Andrei Calin ciutanp Data 22 septembrie 2019 18:02:22
Problema Pairs Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int NAX = 1e6 + 5;

ifstream f("pairs.in");
ofstream g("pairs.out");

ll ciur[ NAX ], ras;
ll n, maxi;
bitset< NAX > in;
bitset< NAX > un_factor_prim;

void self_max(ll &a, ll b)
{
    a = max(a, b);
}

int main()
{
    f >> n;
    for(int x, i = 1 ; i <= n ; ++i)
    {
        f >> x;
        in[ x ] = 1;
        self_max(maxi, x);
    }
    for(int i = 2 ; i <= maxi ; ++i)
        if(ciur[ i ] == 0)
    {
        for(int j = i  ; j <= maxi ; j += i)
        {
            ciur[ j ]++;
            if( j % (i * i ) == 0)
                un_factor_prim[ j ] = true;
        }
    }
    for(int i = 2 ; i <= maxi ; ++i)
        if(un_factor_prim[ i ] == false)
    {
        ll nr = 0;
        for(int j = i ; j <= maxi ; j += i )
        {
            if(in[ j ])
            {
                nr++;
            }
        }
        if( ciur[ i ] % 2 )
            ras += nr * (nr - 1)/2;
        else
            ras -= nr * (nr - 1)/2;
    }
    g << n * ( n - 1 ) / 2 - ras;
}